akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]
#![allow(unused_variables)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let A: Vec<Vec<usize>> = {
        let mut A = vec![];
        for _ in 0..N {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            A.push(
                line.split_whitespace()
                    .map(|x| x.parse().unwrap())
                    .collect()
            );
        }
        A
    };

    // 試合可能なペアについて、可能な限り、その日で試合させる
    let mut R = vec![0; N];
    let mut B: Vec<_> = (0..N)
        .filter(|&i| i == A[A[i][0] - 1][0] - 1 && i < A[i][0] - 1)
        .map(|i| (i, A[i][0] - 1))
        .collect();
    let mut d = 0;
    while !B.is_empty() {
        d += 1;
        let mut T = vec![];
        for &(i, j) in &B {
            R[i] += 1;
            if R[i] < N - 1 {
                let k = A[i][R[i]] - 1;
                if i == A[k][R[k]] - 1 { T.push((i, k)); }
            }
            R[j] += 1;
            if R[j] < N - 1 {
                let k = A[j][R[j]] - 1;
                if j == A[k][R[k]] - 1 { T.push((j, k)); }
            }
        }
        B = T;
    }
    let ans = if R.iter().all(|&r| r == N - 1) {
        d
    } else {
        -1
    };

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


Measured memory_bytes: 12540
import math
def judge(x):
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

X = int(input())
ret = 0
for i in range(X, 10**9):
    if judge(i):
        ret = i
        break
print(ret)


Measured memory_bytes: 2940
#include <cstdio>
int pos[300005]; 
int main()
{
	// freopen("AGC022-D.in", "r", stdin); 
	int n, len; 
	scanf("%d%d", &n, &len); 
	for (int i = 0; i < n; i++)
		scanf("%d", pos + i); 
	long long ans = 1, l = 0, r = 0, arb = 0; 
	for (int i = 0; i < n; i++)
	{
		int t;
		scanf("%d", &t); 
		ans += t / (len << 1); 
		t %= len << 1; 
		if (!t)
			continue; 
		bool f = t <= pos[i] << 1, g = t <= (len - pos[i]) << 1;
		if (i == n - 1)
			ans -= g; 
		else if (f)
		{
			l++; 
			if (g)
				arb++; 
		}
		else if (g)
			r++; 
		while (l - arb < r + arb)
		{
			if (arb)
				arb--;
			else
				r--;
		}
		ans++; 
	}
	printf("%lld\n", (ans - arb - r) * (len << 1));
	return 0; 
}


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

int main(){
  int64_t N,T;
  cin>>N>>T;
  vector<int64_t> a(N);
  for(int i=0;i<N;++i) cin>>a[i];

  //m[i]はa[0]からa[i]までの最小値
  //りんご1個から生じる利益の最大値M
  vector<int64_t> m(N);
  int64_t M=0;
  m[0]=a[0];
  for(int i=1;i<N;++i){
    m[i]=min(m[i-1],a[i]);
    M=max(M,a[i]-m[i-1]);
  }

  int ans=0;
  for(int i=1;i<N;++i){
    if(a[i]-m[i-1]==M) ++ans;
  }

  cout<<ans<<endl;
}


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

int main(){
  int N,C;
  cin>>N>>C;
  const int MAX=100001;
  vector<vector<int>> s(C,vector<int>(MAX)),t(C,vector<int>(MAX));
  for(int i=0;i<C;i++)for(int j=0;j<MAX;j++)s[i][j]=MAX;
  for(int i=0;i<C;i++)for(int j=0;j<MAX;j++)t[i][j]=MAX;
  std::vector<int> v(C,0);
  int x,y,z;
  for(int i=0;i<N;i++){
    cin>>x>>y>>z;
    z--;
    s[z][v[z]]=x;
    t[z][v[z]]=y;
    v[z]++;
  }
  for(int i=0;i<C;i++){
    sort(s[i].begin(),s[i].end());
    sort(t[i].begin(),t[i].end());
    for(int j=1;j<v[i];j++){
      if(t[i][j-1]==s[i][j]){
        s[i][j]=s[i][j-1];
        s[i][j-1]=MAX;
        t[i][j-1]=MAX;
      }
    }
    sort(s[i].begin(),s[i].end());
    sort(t[i].begin(),t[i].end());
  }
  std::vector<int> d(MAX,0);
  for(int i=0;i<C;i++){
    for(int j=0;s[i][j]<MAX;j++){
      d[s[i][j]-1]++;
      d[t[i][j]]--;
    }
  }
  int ans=d[0];
  for(int i=1;i<MAX;i++){
    d[i]+=d[i-1];
    ans=max(ans,d[i]);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 24568
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
const int inf = 1e9+7;
const int N = 1e6+9;

void solve() {
    int a, b, n;
    string s;
    cin>>s;
    if(isupper(s[0])) cout<<"A";
    else cout<<"a";
}
int main() {
    ios_base::sync_with_stdio(0);
    int T=1 ,cas=0;
    while(T--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3596
import numpy as np
def LI(): return list(map(int, input().split()))


N, K = LI()
h = np.array(LI(), dtype='int32')
dp = np.zeros(N, dtype='int32')
 
for i in range(1, N):
  start = 0 if i < K else i-K
  dp[i] = np.min(dp[start:i] + np.abs(h[i]-h[start:i]))
 
print(dp[-1])


"""
"""


Measured memory_bytes: 22820
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<int>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  string s;
  cin >> s;
  int u=0;
  int k=0;
  rep(i,3){
    if(s[i]=='R')k++;
    else k=0;
    u=max(u,k);
  }
  cout << u << endl;
}

Measured memory_bytes: 3620
from collections import deque

n, x, y = map(int, input().split())

g = [[] for _ in range(n)]

for i in range(n - 1):
    g[i].append(i + 1)
    g[i + 1].append(i)
g[x - 1].append(y - 1)
g[y - 1].append(x - 1)


def bfs(g, n_node, start_node):
    dist = [-1] * n_node
    dist[start_node] = 0
    que = deque([start_node])

    while que:
        node = que.popleft()
        for j in g[node]:
            if dist[j] != -1:
                continue
            dist[j] = dist[node] + 1
            que.append(j)
    return dist


ans = [0] * n

for i in range(n):
    dist = bfs(g, n, i)
    for d in dist:
        ans[d] += 1

for a in ans[1:]:
    print(a//2)

Measured memory_bytes: 9848
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> P;

P calc(P a,P b,P c,P d){
  double A=imag((a-d)*conj(d-c));
  double B=imag((b-d)*conj(d-c));
  return a+(b-a)*A/(A-B);
}

int main(){
  int n;
  double ax,ay,bx,by,cx,cy,dx,dy;
  scanf("%d",&n);
  while(n--){
    scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
    P ans=calc(P(ax,ay),P(bx,by),P(cx,cy),P(dx,dy));
    printf("%.8f %.8f\n",ans.real(),ans.imag());
  }
  return 0;
}

Measured memory_bytes: 1256
n = int(input())
a_list = list()
for _ in range(n):
    a_list.append(int(input()))

sorted_a_list = sorted(a_list)

max_v = max(sorted_a_list)

is_max_v_multi = sorted_a_list[-1] == sorted_a_list[-2]

next_max_v = 0
for i in range(len(sorted_a_list) - 1, -1, -1):
    if sorted_a_list[i] != max_v:
        next_max_v = sorted_a_list[i]
        break

for a in a_list:
    if is_max_v_multi:
        print(max_v)
    else:
        if a == max_v:
            print(next_max_v)
        else:
            print(max_v)


Measured memory_bytes: 14176
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//AtCoder Beginner Contest 117
//B	Polygon
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<Integer> in = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			in.add(sc.nextInt());
		}
		sc.close();

		int max = Collections.max(in);
		int sum = 0;
		for (Integer i : in) {
			sum += i;
		}

		System.out.println((sum - max) > max ? "Yes" : "No");

	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define fs first
#define se second
#define M 1000000007
ll exp(ll a,ll p)
{
	if(p==1)
		return a;
	if(p==0)
		return 1;
	ll st=exp(a,p/2);
	st=(st*st)%M;
	if(p%2 != 0)
		st=(st*a)%M;
	return st;
} 
int solve(int A, int B, int C) {
    ll mn=0,mx=1e18;
    ll ans=INT_MAX,mid;
    ll g=__gcd(A,B);
    ll l=(A*B)/g;
    cout<<l<<endl;
    while(mn<=mx)
    {
        mid=mn+(mx-mn)/2;
        ll f2=mid/A;
        ll f3=mid/B;
        ll f4=mid/l;
        ll t=f2+f3-f4;
        cout<<mid<<" "<<t<<endl;
        if(t>=A)
        {
            mx=mid-1;
            ans=min(mid,ans);
        }
        else 
        {
            mn=mid+1;
        }
        
    }
    return ans%M;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// ll t;
	// cin>>t;
	// while(t--)
	// {
		
	// }
	ll k,x;
	cin>>k>>x;
	if(k*500 >= x)
		cout<<"Yes";
	else
		cout<<"No";
	cout<<endl;

}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, m;

int main() {
	cin >> n >> m;
	
	LL ans;
	
	if(n == 1 && m == 1) { ans = 1; }
	if(n != 1 && m == 1) { ans = n - 2; }
	if(n == 1 && m != 1) { ans = m - 2; }
	if(n != 1 && m != 1) { ans = (n - 2) * (m - 2); }
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (max(A) + 1)
ans = 1
for a in A:
    if a > 0:
        ans *= counts[a - 1]
        ans %= MOD
        counts[a - 1] -= 1
    counts[a] += 1
c0 = A.count(0)
if c0 == 1:
    print(ans * 3 % MOD)
elif c0 in (2, 3):
    print(ans * 6 % MOD)
else:
    print(0)


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

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

const int MAX_DIGIT = 50;
ll dp[100][2];

int main(void){
  int n;
  ll k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  rep(d, MAX_DIGIT) {
    ll mask = 1LL << (MAX_DIGIT - d - 1);

    int num = 0;
    rep(i, n) {
      if (a[i] & mask) ++num;
    }
    ll cost0 = mask * num;
    ll cost1 = mask * (n - num);

    if (dp[d][1] != -1) {
      dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(cost0, cost1));
    }
    if (dp[d][0] != -1) {
      if (k & mask) {
	dp[d+1][1] = max(dp[d+1][1], dp[d][0] + cost0);
      }
    }
    if (dp[d][0] != -1) {
      if (k & mask) {
	dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost1);
      } else {
	dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost0);
      }
    }
  }
  cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]) << endl;
  return 0;
}


Measured memory_bytes: 1024
n = int(input())
a = list(map(lambda x:int(x) - 1, input().split()))
jousi = [-1 for _ in range(n)]
for i in range(n-1):
    jousi[i + 1] = a[i]

buka = [0 for _ in range(n)]
for i in jousi:
    if i >= 0:
        buka[i] += 1

print(*buka, sep = '\n')

Measured memory_bytes: 32372
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int k = sc.nextInt();
    
    if (n % k == 0) {
      System.out.println(0);
    } else {
      System.out.println(1);
    }
  }
}

Measured memory_bytes: 22740
#include <stdio.h>
#include <stdlib.h>
#define ll long long

typedef struct{
  ll A;
  int B;
}energy;
int cmp(const void *p,const void *q){
  return ((energy*)p)->A-((energy*)q)->A;
}
void init(energy *t,int N);

int main(){
  int N,M;
  energy *E;
  ll ans=0;
  int i;

  scanf("%d%d",&N,&M);
  E=(energy*)malloc(sizeof(energy)*N);

  init(E,N);
  qsort(E,N,sizeof(energy),cmp);

  i=0;
  while(M>0){
    if(E[i].B<=M){
      ans+=E[i].A*E[i].B;
      M-=E[i].B;
    }else{
      ans+=M*E[i].A;
      break;
    }
    i++;
  }
  printf("%lld\n",ans);

  free(E);
  return 0;
}

void init(energy *t,int N){
  for(int i=0;i<N;i++)scanf("%lld%lld",&t[i].A,&t[i].B);
}

Measured memory_bytes: 3324
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))

city = a[1]
array = [1, a[1]]
checked = [False for _ in range(n+1)]
checked[1] = True
while True:
  tmp = a[city]
  city = tmp
  if checked[city]:
    break
  else:
    checked[city] = True
    array.append(tmp)
p = array.index(city)
q = len(array) - p
if k > p:
  print(array[p+(k-p)%q])
else:
  print(array[k])


Measured memory_bytes: 32308
let a, b, k = stdin.ReadLine().Split() |> fun x -> int x.[0], int x.[1], int x.[2]
let c = [for i in 1..a -> if a % i = 0 then i else 1] |> List.distinct |> Set.ofList
let d = [for i in 1..b -> if b % i = 0 then i else 1] |> List.distinct |> Set.ofList
let f = Set.intersect c d |> Set.toList |> List.rev
printfn "%d" f.[k - 1]

Measured memory_bytes: 15068
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N, K = MI()
    ans = 0

    for i in range(K, N+2):
        mx = (N + (N - i + 1)) * i // 2
        mn = (i - 1) * i // 2
        # print(N, N - i + 1)
        # print(i, mn, mx)
        ans += mx - mn + 1
        ans %= MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()


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

int main(){
    int k,n;
    cin>>k>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a.at(i);
    }
    int m;//隣り合った家の幅の最大値
    m=k-a.at(n-1)+a.at(0);
    for(int i=1;i<n;i++){
        if(m<a.at(i)-a.at(i-1)) m=a.at(i)-a.at(i-1);        
    }
    cout<<k-m<<endl;
}

Measured memory_bytes: 1024
//abc057_b.cpp
//Sat Oct 27 20:44:56 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	for (int i=0;i<n;i++){
		int ans = -1;
		int dis = INTINF;
		for (int j=0;j<m;j++){
			if (abs(a[i]-c[j])+abs(b[i]-d[j])<dis){
				ans = j;
				dis = abs(a[i]-c[j])+abs(b[i]-d[j]);
			}
		}
		cout << ans +1 << endl;
	}

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a[100020],x,b[100020],sum=1,lmin=1000000000,j;
int main()
{
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	if(a[1]==1000000000){cout<<999999999;return 0;}
	for(int i=1;i<=n;i++)
	{
	    if(a[i]>x)b[i]=a[i]-x;
		if(a[i]<x)b[i]=x-a[i];
		lmin=min(b[i],lmin);
	}
	sort(b+n,b+1+n);
	for(int i=2;i<=lmin;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(b[j]%i!=0)break;
		}
		if(j>n)sum=i;
	}
	cout<<sum;
	return 0;
}

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

int main(){
  ll N;
  string S;
  cin >> N >> S;
  if( N%2==1 ){
    cout << "No" << endl;
    return 0;
  }
  string T="";
  for(ll i=0;i<N/2;i++){
    T+=S.at(i);
  }
  if(S==T+T){
    cout << "Yes" << endl;
    return 0;
  }
  else{
    cout << "No" << endl;
    return 0;
  }
}



Measured memory_bytes: 3628
if __name__ == "__main__":
    N, M = list(map(int, (input().split(' '))))
    ura = 0
    if N == 1 and M != 1:
        arr = [0 for i in range(N)]
        ura = M - 2
    elif N != 1 and M == 1:
        arr = [0 for i in range(M)]
        ura = N - 2
    elif N == 1 and M == 1:
        ura = 1
    else:
#        arr = [[0 for i in range(M)] for j in range(N)]
#        for i in range(N):
#            for j in range(M):
#                for buf_i in range(-1, 2):
#                    for buf_j in range(-1, 2):
#                        if i-buf_i < 0 or i+buf_i >= N or j-buf_j < 0 or j+buf_j >= M:
#                            continue
#                        if arr[i+buf_i][j+buf_j] == 0:
#                            arr[i+buf_i][j+buf_j] = 1
#                        else:
#                            arr[i+buf_i][j+buf_j] = 0
#        for i in range(N):
#            for j in range(M):
#                if arr[i][j] == 1:
#                    ura += 1
        ura = N * M - (N * 2 + M * 2 - 4)
    print(ura)

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

using ll = long long;
const int maxn = 16;

int n;
struct pt {
    ll x, y, p;
    void read() {
        scanf("%lld%lld%lld", &x, &y, &p);
    }
} p[maxn];

ll d[1 << maxn][maxn][2], ans[maxn];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        p[i].read();
    }
    for(int i = 0; i <= n; ++i) {
        ans[i] = 1e18;
    }
    for(int s = 0; s < (1 << n); ++s) {
        for(int i = 0; i < n; ++i) {
            d[s][i][0] = std::abs(p[i].x);
            d[s][i][1] = std::abs(p[i].y);
            for(int j = 0; j < n; ++j) {
                if(~s & (1 << j))
                    continue;
                d[s][i][0] = std::min(d[s][i][0], std::abs(p[i].x - p[j].x));
                d[s][i][1] = std::min(d[s][i][1], std::abs(p[i].y - p[j].y));
            }
        }
    }
    for(int s = 0; s < (1 << n); ++s) {
        int w = __builtin_popcount(s);
        for(int u = s; u >= 0; u = (u - 1) & s) {
            int v = s ^ u;
            ll tot = 0;
            for(int i = 0; i < n; ++i) {
                tot += p[i].p * std::min(d[u][i][0], d[v][i][1]);
            }
            ans[w] = std::min(ans[w], tot);
            if(u == 0)
                break;
        }
    }
    for(int i = 0; i <= n; ++i) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Measured memory_bytes: 11988
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count = 0

for i in range(N):
    if B[i] >= A[i] + A[i+1]:
        count += A[i] + A[i+1]
        A[i+1] = 0
    else:
        if B[i] > A[i]:
            count += B[i] 
            A[i+1] = A[i+1] - (B[i] - A[i])
        else:
            count += B[i]

print(count)

Measured memory_bytes: 18624
#include <bits/stdc++.h>
using namespace std;
#define MODNUMBER 1000000007

long long pow_mod(int a, int n) {  // a^n mod MODNUMBER
	long long result = 1;
	int i = 0;
	long long a_i = a;
	int n_tmp = n;
	while (n_tmp > 0) {
		if (n_tmp & 0b1) {
			result = (result * a_i) % MODNUMBER;
			// cout << result << "\n";
		}
		a_i = a_i * a_i % MODNUMBER;
		n_tmp = n_tmp >> 1;
	}
	return result;
}

long long fact_mod(int k) {  // k! mod MODNUMBER

	long long result = 1;
	for (int i = 1; i <= k; i++) {
		result = (result * i) % MODNUMBER;
	}
	return result;
}

long long inv_mod(int k) {  // k^(-1) mod MODNUMBER

	return pow_mod(k, MODNUMBER - 2);
}

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

	int n, a, b;
	scanf("%d %d %d", &n, &a, &b);

	long long all_num = pow_mod(2, n);

	// cout << all_num << "\n";

	// long long cov_a = n! / ((n-k)!*k!)

	// long long fact_mod_n = fact_mod(n);
	// cout << fact_mod_n << "\n";
	// cout << inv_mod(fact_mod(n - a) * fact_mod(a) % MODNUMBER) << "\n";
	/*
	    long long cov_a =
	        (fact_mod_n * inv_mod(fact_mod(n - a) * fact_mod(a) % MODNUMBER)) %
	        MODNUMBER;
	*/

	long long cov_a = 1;
	for (int i = n; i > n - a; i--) {
		cov_a = (cov_a * i) % MODNUMBER;
	}
	cov_a = (cov_a * inv_mod(fact_mod(a))) % MODNUMBER;

	// cout << cov_a << "\n";

	/*
	    long long cov_b =
	        (fact_mod_n * inv_mod(fact_mod(n - b) * fact_mod(b) % MODNUMBER)) %
	        MODNUMBER;
	*/

	long long cov_b = 1;
	for (int i = n; i > n - b; i--) {
		cov_b = (cov_b * i) % MODNUMBER;
	}
	cov_b = (cov_b * inv_mod(fact_mod(b))) % MODNUMBER;

	// cout << cov_b << "\n";

	long long result = (all_num - cov_a - cov_b - 1) % MODNUMBER;
	if (result < 0) {
		result += MODNUMBER;
	}
	cout << result << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,a) FOR(i,0,(int)(a)-1)
#define reset(a,b) memset(a,b,sizeof(a))
#define BUG(x) cout << #x << " = " << x << endl
#define PR(x,a,b) {cout << #x << " = "; FOR (_,a,b) cout << x[_] << ' '; cout << endl;}
#define CON(x) {cout << #x << " = "; for(auto i:x) cout << i << ' '; cout << endl;}
#define mod 1000000007
#define pi acos(-1)
#define eps 0.00000001
#define pb push_back
#define sqr(x) (x) * (x)
#define _1 first
#define _2 second

long long n, lis[100005];

int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  long long s = 0;
  long long tmp = n * (n + 1) / 2;
  REP (i, n) cin >> lis[i], s += lis[i];
  if (s % tmp) {
  	cout << "NO";
  	return 0;
  }
  s /= tmp;
  long long ans = 0;
  REP (i, n) {
  	tmp = lis[(i + 1) % n] - lis[i];
  	long long k = (s - tmp) / n;
  	if ((s - tmp) % n || k < 0 || k > s) {
  		cout << "NO";
  		return 0;
  	}
  	ans += k;
  }
	if (ans != s) {
		cout << "NO";
		return 0;
	}
  cout << "YES";
}

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

using namespace std;

const long long MOD = 1000000007;

int GCD(int a, int b){return b == 0 ? a : GCD(b, a % b);}

long long digits(long long n){
    return log10(n) + 1;
}

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);

    long long n;
    cin >> n;

    long long best = 1e9;

    for(long long i = 1; i * i <= n; ++i){
        if(n % i == 0){
            best = min(max(digits(i), digits(n / i)), best);
        }
    }

    cout << best;

    return 0;
}


Measured memory_bytes: 640
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		int a = in.nextInt();
		int b = in.nextInt();
		if (a > 0) {
			out.println("Positive");
		} else if (a <= 0 && 0 <= b) {
			out.println("Zero");
		} else if (b < 0) {
			out.println((b-a)%2 == 1 ? "Positive" : "Negative");
		}
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

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

ll digit_sum( ll n ){
    if( n<10 ) return n;
    return n%10 + digit_sum( n/10 );
}

int main(){
    string N;
    cin >> N;
    int sum = 0;
    rep( i, N.length() ) sum += N[i] - '0'; // treat bit
    if( sum%9 == 0 ) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3732
import java.util.*;

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

		long min = N + 1;
		for (int i = 2; i <= Math.sqrt(N); i++) {
			long temp = i + (N / i);
			if ((N % i == 0) && (temp < min)) {
				min = temp;
			}
		}
		System.out.println(min - 2);
	}
}


Measured memory_bytes: 23892
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

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

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] k = new int[M];
        List<Integer>[] S = new ArrayList[M];
        int[] p = new int[M];
        for (int i=0; i<M; i++) {
            k[i] = sc.nextInt();
            S[i] = new ArrayList<>();
            for (int j=0; j<k[i]; j++) {
                S[i].add(sc.nextInt());
            }
        }
        for (int i=0; i<M; i++) {
            p[i] = sc.nextInt();
        }

        System.out.println(solve(N, M, k, S, p));
    }

    public static int solve(int N, int M, int[] k, List<Integer>[] s, int[] p) {
        int count = 0;

        for (int i=0; i<Math.pow(2, N); i++) {
            boolean on = true;
            for (int j=0; j<M; j++) {
                if (!isOn(N, i, k[j], s[j], p[j])) {
                    on = false;
                    break;
                }
            }
            // System.err.println("i=" + i + ", on = " + on);
            if (on) count++;
        }

        return count;
   }

   private static boolean isOn(int N, int state, int k, List<Integer> s, int p) {
        int count = 0;

        for (int i=0; i<k; i++) {
            count += getStatus(state, s.get(i));
        }

        // System.err.println("state=" + state + ", count=" + count + ", p=" + p);
        return count%2 == p;
   }

   private static int getStatus(int status, int idx) {
        // System.err.println("status=" + status + " index=" + idx + " is " + ((status>>idx)%2));
        return (status >> (idx-1)) %2;
   }
}

Measured memory_bytes: 23892
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int n,i,j,k;
	cin>>n>>k;
	if(n>=10) cout<<k;
	else {
		cout<<(10-n)*100+k;
		
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
  using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define endl "\n"
  #define int long long
  #define all(v) v.begin(),v.end()
  #define f first
  #define s second
  #define PB push_back
  #define MP make_pair
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  #define MOD 998244353
  #define N 200005
  #define INF 1000000000000
  #define eps 1e-6

  bool custom(pair<int,int> &a,pair<int,int> &b)
  {
    if(a.s == b.s)return a.f > b.f;
    return a.s > b.s;
  }
int32_t main()
{
    IOS

  int n;
  cin >> n;
  int arr[n+1];

  for(int i = 1; i <= n; i++)
  {
    cin >> arr[i];
  }

  int x =0;

  for(int i = n; i >=1; i--)
  {
    if(i%2 == 1)
    {
      x += arr[i];      
    }
    else
    {
      x-= arr[i];
    }
  }

  
  cout << x << " ";
  x/=2;
  vector<int> ans;

  for(int i = 1; i <= n-1; i++)
  {
    ans.PB(arr[i]-x);
    x = arr[i] - x;
  }

  for(auto i: ans)
  {
    cout << 2*i << " ";
  }

	return 0;  
}

Measured memory_bytes: 3060
using System;
class p
{
  static void Main()
  {
    string s = Console.ReadLine();
    Console.WriteLine((((s[0] == s[1]) && (s[1] == s[2])) || ((s[1] == s[2]) && (s[2] == s[3]))) ? "Yes" : "No");
  }
}

Measured memory_bytes: 13140
main = do
  [a,b,c] <- map read . words <$> getLine
  print $ solve (a,b,c) 0

solve :: (Int,Int,Int) -> Int -> Int
solve (a,b,c) k
  | a `mod` 2 == 1 || b `mod` 2 == 1 || c `mod` 2 == 1 = k
  | a == b && b == c = -1
  | otherwise = solve ((a+b) `div` 2,(a+c)`div`2,(b+c)`div`2) (k+1)

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

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

  int sq = sqrt(N);

  int a = 1;
  for(int s = sq;s >= 1;s--){
    if(N%s == 0){
      a = s;
      break;
    }
  }

  std::cout << (a - 1 + (N/a - 1)) << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define ll long long
//vector<int> g1;
//g1.push_back(i);

using namespace std;

int main()
{
	ll a,b,c;
	cin >> a >> b >> c;
	if (c>a)
	{
		if(b+a-c<0) cout << 0 << " " << 0;
		else cout << 0 << " " << b+a-c;
	}
	else
	{
		cout << a-c << " " << b;
	}
}



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

using namespace std;
using ll = long long;

int main(){
	string s = {};
	cin >> s;

	if(s[0] == s[1] && s[2] == s[3] && s[0] != s[2]){
		cout << "Yes" << endl;
	}else if(s[0] == s[3] && s[1] == s[2] && s[0] != s[1]){
		cout << "Yes" << endl;
	}else if(s[0] == s[2] && s[1] == s[3] && s[0] != s[1]){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int health[10005];
int main()
{
	int H,n;
	int Ai,Bi;
	cin>>H>>n;
	int tmp,ind;
	for(int j=0;j<=H;j++)health[j]=j*10000;
	for(int i=0;i<n;i++)
	{
		cin>>Ai>>Bi;
		for(int j=1;j<=H;j++)
		{
			if(j>=Ai)ind=j-Ai;else ind=0;
			tmp=health[ind]+Bi;
			if(tmp<health[j])health[j]=tmp;
		}
	}
	cout<<health[H];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <sstream>
#include <iterator>
#include <complex>
using namespace std;

long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcd(long long a,long long b){return a*b / gcd(a,b) / gcd(a,b);}
int main()
{
	int N;
	cin>>N;

	set<string> s;
	for(int i=0; i<N; i++)
	{
		string _s;
		cin>>_s;

		s.insert(_s);
	}
	cout<<s.size()<<endl;

}

Measured memory_bytes: 19200
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = inp()
D,X = inpl()
ans = 0
for i in range(N):
	a = inp()
	ans += (D-1)//a+1

print(ans+X)


Measured memory_bytes: 4204
package main

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

func newScanner() *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	// buf := make([]byte, 10000)
	// scanner.Buffer(buf, 1000000)
	return scanner
}

func scanInt(s *bufio.Scanner) int {
	if s.Scan() {
		t := s.Text()
		v, err := strconv.Atoi(t)
		if err == nil {
			return v
		}
		panic(err)
	} else {
		panic(s.Err())
	}
}

func scanString(s *bufio.Scanner) string {
	if s.Scan() {
		return s.Text()
	}
	panic(s.Err())
}

func main() {
	sc := newScanner()
	an := scanInt(sc)
	bn := scanInt(sc)
	m := scanInt(sc)

	aMin := 100000
	bMin := 100000
	cMin := math.MaxInt32

	a := make([]int, an)
	b := make([]int, bn)

	for i := 0; i < an; i++ {
		a[i] = scanInt(sc)
		if a[i] < aMin {
			aMin = a[i]
		}
	}

	for i := 0; i < bn; i++ {
		b[i] = scanInt(sc)
		if b[i] < bMin {
			bMin = b[i]
		}
	}

	for i := 0; i < m; i++ {
		x := scanInt(sc)
		y := scanInt(sc)
		c := scanInt(sc)
		p := a[x-1] + b[y-1] - c
		if p < cMin {
			cMin = p
		}
	}

	if aMin+bMin < cMin {
		fmt.Println(aMin + bMin)
	} else {
		fmt.Println(cMin)
	}

}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using piii = pair<int, pair<int, int>>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;

ll sum(vector<ll> &vsum) {
    int siz = vsum.size();
    ll res = 0;
    for (int i = 1; i < siz; ++i) {
        ll v = vsum[i] - vsum[i - 1];
        res += (i - 1) * v - vsum[i - 1];
        res %= MOD;
    }
    return res;
}

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

    int n, m;
    cin >> n >> m;
    vector<ll> xsum(n + 1), ysum(m + 1);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        xsum[i + 1] = (xsum[i] + x) % MOD;
    }
    for (int i = 0; i < m; ++i) {
        int y;
        cin >> y;
        ysum[i + 1] = (ysum[i] + y) % MOD;
    }

    ll ans = sum(xsum) * sum(ysum) % MOD;
    if (ans < 0)
        ans += MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
int main(void)
{
	int r;
	int g;
	int b;
	int n;
	int x;
	int y;
	int temp;
	int res;

	scanf("%d%d%d%d", &r,&g,&b,&n);
	res = 0;
	x = 0;
	while (x <= n)
	{
		y = 0;
		while (y <= n)
		{
			temp = n - r*x - g*y;
			if (temp >= 0 && temp % b == 0)
			{
				res++;
			}
			y++;
		}
		x++;
	}
	printf("%d\n", res);
	return (0);
}


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

int32_t main()
{
	int n,k;
	cin>>n>>k;
	vector<int> v(n);
	for(int i=0;i<n;i++) cin>>v[i];
	sort(v.begin(),v.end());
	long long mn=8000000000000000000LL;
	//cout<<mn<<"\n";
	for(int i=k-1;i<n;i++) mn=min(mn,v[i]-v[i-k+1]);
	cout<<mn<<"\n";
	return 0;
}

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

typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K, A, B;
    cin >> K >> A >> B;
    bool flag = false;
    for (int i=A;i<=B;i++){
        if (i%K==0) flag =true;
    }
    if (flag) cout << "OK" << "\n";
    else cout << "NG" << "\n";
}

Measured memory_bytes: 3652
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int A[maxn],cnt = 0,
B[maxn],C[maxn],ans=0;
int check(int x)
{
    memset(A,0,sizeof(A));
    cnt = 0;
    if(x != 0)
    while(x)
    {
       A[cnt++] = x%10;
       x/=10;
    }
    else{
        A[0] = 0;
        cnt++;
    }
    for(int i=0;i<cnt;i++){
        for(int j=0;j<ans;j++ ){
            if(A[i] == C[j])
                return 0;
        }

    }
    return 1;

}
int main()
{
    int n,sum;
    cin>>sum>>n;
    memset(B,0,sizeof(B));
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        B[temp] = 1;
    }
    ans = 0;
    for(int i=0;i<10;i++)
    {
        if(B[i]==1)
            C[ans++]=i;
    }
    for(int i=sum;i<100010;i++)
    {
        if(check(i)){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var s string
	fmt.Scan(&s)
	count := 0
	for _, v := range s{
		num, _ := strconv.Atoi(string(v))
		count += num
	}
	if count % 9 == 0{
		fmt.Println("Yes")
	}else{
		fmt.Println("No")
	}
}

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s[200];
	string l="",t="";
    int n;
    cin>>n;
    cin>>t;
    int j=2;
    s[1]=t;
    for(int i=2;i<=n;i++)
    {
    	l=t;
    	cin>>t;
    	if(t[0]!=l[l.size()-1])
    	{
    		cout<<"No"<<endl;
    		return 0;
    	}
    	for(int i=1;i<j;i++)
    	{
    		if(s[i]==t)
    		{
    			cout<<"No"<<endl;
    		    return 0;
    		}
    		
    	}
    	s[j]=t;
    	j++;
    }
    cout<<"Yes"<<endl;
	return 0;
}

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

//#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD = 1e9 + 7;

signed main() {
	for (int A, B; cin >> A >> B && (A || B);) {
		int c[3] = {};
		int diff = B - A;
		c[2] = diff / 1000;
		diff %= 1000;
		c[1] = diff / 500;
		diff %= 500;
		c[0] = diff / 100;
		cout << c[0] << " " << c[1] << " " << c[2] << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
		int H = scan.nextInt();
		int W = scan.nextInt();
		if(H==0&&W==0) break;
		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++){
				if(i==0||i==H-1||j==0||j==W-1)System.out.print("#");
				else System.out.print(".");
			}
			System.out.println();
		}
		System.out.println();
		
		}
	}

}

Measured memory_bytes: 24636
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        String s = in.ns();
        if(s.equals("ABC"))out.println("ARC");
        else out.println("ABC");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

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

int main() {
  int n, k;
  cin >> n >> k;
  if (k > n * (n - 1) / 2 - (n - 1)) {
    // 連結なグラフであるから自明にn-1個の最短経路が1の頂点の組がある
    cout << -1 << endl;
    return 0;
  }
  int prc = (n - 1) * (n - 2) / 2 - k;
  // 操作回数
  cout << prc + (n - 1) << "\n";
  for (int i = 2; i <= n; i++) {
    cout << 1 << " " << i << "\n";
  }
  int count = 0;
  for (int i = 2; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (count >= prc) {
        i = n;
        j = n;
        continue;
      }
      cout << i << " " << j << "\n";
      count++;
    }
  }
}


Measured memory_bytes: 256
// aribon4-3_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;



struct SCC {

    int N;
    vector<int> tmp_order;
    vector<int> scc_group;
    vector<bool> used;
    vector<vector<int>> edges, rev_edges;

    SCC(int n): N(n), edges(n), rev_edges(n), scc_group(n, -1), used(n) {}

    void add_edge(int u, int v){
        edges[u].emplace_back(v);
        rev_edges[v].emplace_back(u);
    }

    void dfs(int i){
        used[i] = true;
        for (auto v: edges[i]){
            if (used[v]) continue;
            dfs(v);
        }
        tmp_order.emplace_back(i);
    }

    void dfs2(int i, int k){
        used[i] = true;
        scc_group[i] = k;
        for (auto v: rev_edges[i]){
            if (used[v]) continue;
            dfs2(v, k);
        }
    }

    int calc_scc(){

        REP(i, N){
            if (used[i]) continue;
            dfs(i);
        }

        used.assign(N, false);
        int k = 0;
        REP(i, N){
            int v = tmp_order[N-i-1];
            if (used[v]) continue;
            dfs2(v, k++);
        }

        return k;
    }
};

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, E;
    cin >> N >> E;

    SCC g(N);
    REP(i, E){
        int s, t;
        cin >> s >> t;
        g.add_edge(s, t);
    }

    g.calc_scc();

    int Q;
    cin >> Q;
    REP(i, Q){
        int u, v;
        cin >> u >> v;
        int ans = int(g.scc_group[u] == g.scc_group[v]);
        print(ans);
    }

    return 0;
}



Measured memory_bytes: 4452
#include<bits/stdc++.h>
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag,
         tree_order_statistics_node_update>;
*/

struct Edge {
	int a, b, v;
	
	bool operator < (const Edge& e) const {
		return v < e.v;
	}
	friend istream& operator >> (istream& in, Edge& e) {
		return in >> e.a >> e.b >> e.v;
	}
};
vector<Edge> edges;

constexpr int maxn = 100005;

int n, m, fu[maxn], cnt_edg[maxn];
LL x[maxn];
bool ok[maxn];

int fin(int a) {
	return fu[a] == a ? a : fu[a] = fin(fu[a]);
}

void un(int a, int b) {
	if(a == b) return;
	x[a] += x[b];
	cnt_edg[a] += cnt_edg[b];
	fu[b] = a;
}

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

	cin >> n >> m;
	for(int i=1; i<=n; i++)
		cin >> x[i];
	edges.resize(m);
	for(auto& e:edges)
		cin >> e;
	
	sort(all(edges));
	iota(fu, fu+n+1, 0);
	int ans = 0;
	for(int i=0; i<m; i++) {
		auto& e = edges[i];
		auto a = fin(e.a), b = fin(e.b);
		un(a, b);
		cnt_edg[a]++;
		if(x[a] >= e.v) {
			ans += cnt_edg[a];
			cnt_edg[a] = 0;
		}
	}
	
	cout << m - ans << "\n";
		
	




	return 0;
}


Measured memory_bytes: 2944
# /user/bin/python
# -*- coding: utf-8 -*-
import sys

s = str(input())
k = int(input())

i_r = 0
k_str = []
nm = 0
for i_l in range(len(s)):
  i_r = i_l+1
  while i_r <= len(s):
    nm += 1
    if len(k_str) < k:
      k_str.append(s[i_l:i_r])
      k_str = sorted(k_str)
    elif (s[i_l:i_r] not in k_str) and (k_str[-1] >= s[i_l:i_r]):
      k_str[-1] = s[i_l:i_r]
      k_str = sorted(k_str)

    if k_str[-1] < s[i_l:i_r]:
      i_r = len(s)
    i_r += 1

print(k_str[-1])

Measured memory_bytes: 3064
#include<stdio.h>
#include<ctype.h>
#include<string.h>

int main(){
  int i,j,len;
  char name[500],type,ntype;
  do{
    scanf("%s %c",name,&type);
    if(type=='X') break;
    len=strlen(name);
    if(strchr(name,'_')){
      ntype='D';
    }else if(isupper(name[0])){
      ntype='U';
    }else{
      ntype='L';
    }
    if(type!=ntype){
      name[0]=toupper(name[0]);
      if(ntype=='D'){
	for(i=0;i<len;i++){
	  if(name[i]=='_'){
	    name[i+1]=toupper(name[i+1]);
	    for(j=i+1;name[j];j++) name[j-1]=name[j];
	    name[j-1]=name[j];
	    len--;
	  }
	}
      }
      if(type=='L'){
	name[0]=tolower(name[0]);
      }else if(type=='D'){
	name[0]=tolower(name[0]);
	for(i=1;i<len;i++){
	  if(isupper(name[i])){
	    name[i]=tolower(name[i]);
	    for(j=len+1;j>i;j--) name[j]=name[j-1];
	    name[j]='_';
	    len++;
	  }
	}
      }
    }
    printf("%s\n",name);
  }while(1);
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <string>
#include <map>

using namespace std;

char get_winning(char x) {
	if (x == 'r')
		return 'p';
	else if (x == 's')
		return 'r';
	else 
		return 's';
}

int main()
{
	int n, k, r, s, p;
	string t;
	cin >> n >> k >> r >> s >> p >> t;

	map<char, int> m;
	m['p'] = p;
	m['r'] = r;
	m['s'] = s;

	string sol;

	int sum = 0;
	for (int i = 0; i < n; ++i) {
		char win = get_winning(t[i]);
		if (i - k < 0) {
			sum += m[win];
			sol.push_back(win);
		} else {
			if (win != sol[i - k]) {
				sum += m[win];
				sol.push_back(win);
			}
			else {
				sol.push_back('x');
			}
		}
	}
	// cout << sol;
	// cout << endl;
	cout << sum;
}


Measured memory_bytes: 640