akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_ON(bit, i) (bit & (1LL << i))

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> using VVVV = std::vector<std::vector<std::vector<std::vector<T>>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }
template<class T> inline std::vector<T> unique(std::vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}
// 初項s, 交差dのn個の数列の和
long long sum_of_arithmetic_progression(long long s, long long d, long long n) {
    return n * (2 * s + (n - 1) * d) / 2;
}

const int INF = 1 << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = {0, -1, 0, 1}, dx4 = {1, 0, -1, 0};
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;


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

	int N, K;
	cin >> N >> K;
	V<int> A(N);
	FOR(i, 0, N) {
	    cin >> A[i];
	}

	V<int> dp(100010);
	dp[0] = 0;
	FOR(i, 1, K + 1) {

	    int win = 0;
	    FOE(a, A) {
            if (i >= a) {
                if (dp[i - a] == 0) {
                    win = 1;
                }
            }
	    }
	    dp[i] = win;
	}

	if (dp[K] == 1) {
	    print("First");
	}
	else {
	    print("Second");
	}

	return 0;
}

Measured memory_bytes: 764
import scala.io.StdIn


object Main extends App {
  val Array(n, k)  = StdIn.readLine().split(" ").map(_.toInt)
  val s  = StdIn.readLine()

  def solve(k: Int, s : String): String = {
    s.zipWithIndex.foldLeft("") { (acc, v) =>
      if (v._2 == k - 1) acc + v._1.toString().toLowerCase() else  acc + v._1.toString()
    }

  }


  println(solve(k, s))

}
  




Measured memory_bytes: 25676
#include <bits/stdc++.h>
using namespace std;
int A[3][3];
vector<int> founded;
int isElementExist(int row, int column, int arr[][3], int searchThis){
    int found = 0;
    for(int i=0;i<row;i++){
        for(int j=0;j<column;j++){
            if(searchThis == arr[i][j]){
                return 1;
            }
        }
    }

    return 0;
}

int isVecElementExist(vector<int>& v, int searchThis){
    int found = 0;
    for(int i=0;i<v.size();i++){
        if(v[i] == searchThis){
            return 1;
        }
    }

    return 0;
}
int check(int i,int j){
    if(isVecElementExist(founded,A[i-1][j-1]) ){
        return 1;
    }else{
        return 0;
    }
}
int isBingo(){
    if(check(1,1) && check(1,2) && check(1,3)){
        return 1;
    }
    else if(check(2,1) && check(2,2) && check(2,3)){
        return 1;
    }
    else if(check(3,1) && check(3,2) && check(3,3)){
        return 1;
    }
    else if(check(1,1) && check(2,1) && check(3,1)){
        return 1;
    }
    else if(check(1,2) && check(2,2) && check(3,2)){
        return 1;
    }
    else if(check(1,3) && check(2,3) && check(3,3)){
        return 1;
    }
    else if(check(1,1) && check(2,2) && check(3,3)){
        return 1;
    }
    else if(check(1,3) && check(2,2) && check(3,1)){
        return 1;
    }
    else{
        return 0;
    }
}

int main(){

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin >> A[i][j];
        }
    }

    int N;
    cin >> N;
    int Ns[N];

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

    for(int i=0;i<N;i++){
        if(isElementExist(3,3,A,Ns[i])){
            founded.push_back(Ns[i]);
        }
    }

    if(isBingo()){
        cout << "Yes";
    }else{
        cout << "No";
    }




    return 0;
}


Measured memory_bytes: 256
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
#if l[i] == l[j]: continue
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
flag = 0

for i in range(n-2):
    if d[i][0] == d[i][1] and d[i+1][0] == d[i+1][1] and d[i+2][0] == d[i+2][1]:
        print("Yes")
        flag = 1
        break

if flag == 0:
    print("No")


Measured memory_bytes: 9192
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]
#![allow(clippy::suspicious_arithmetic_impl)]

// using Rust(1.42.0)
// My Library Repo is at "https://github.com/Loptall/prcn_lib"
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"

/*
    AtCoder Language Update 2020204 お疲れ様でした! 有難いです(p.s. 過去問対応もありがとうございます)
*/

// from std...
use std::cmp::{
    max, min,
    Ordering::{Equal, Greater, Less},
};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::mem::swap;
use std::ops::*;
use std::usize::{MAX, MIN};
use std::{i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_integer::{binomial, gcd, lcm, Integer};
use permutohedron::Heap;
use petgraph::unionfind::UnionFind;
use proconio::{fastout, input, is_stdin_empty, marker::*};
use rand::random;

// code...
// #[fastout]
fn main() {
    input! {
        n: usize
    }

    let ans = match n % 10 {
        2 | 4 | 5 | 7 | 9 => "hon",
        0 | 1 | 6 | 8 => "pon",
        _ => "bon"
    };

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


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

int main () {
  int N , M ;
  cin >> N >> M ;
  int board[N][N] = {} ;
  
  for(int i = 0 ; i < M ; i++ ) {
    int a, b ;
    cin >> a >> b ;
    board[a-1][b-1]++ ;
    board[b-1][a-1]++ ;
  }
  
  for(int i = 0 ; i < N ; i++ ) {
    int ans = 0 ;
    for(int j = 0 ; j < N ; j++ ) {
      ans += board[i][j] ;
    }
    cout << ans << endl ;
  }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

// 2018-08-01T21:47:17+0800
// 2018-08-01T21:53:36+0800
// 2018-08-01T22:00:04+0800
func main() {
	var N, K int
	fmt.Scanf("%d%d", &N, &K)
	m := make(map[int]int)
	A := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &A[i])
		m[A[i]] ++
	}
	if len(m) <= K {
		fmt.Println(0)
		return
	}
	n := make([]int, len(m))
	i := 0
	for _, value := range m {
		n[i] = value
		i++
	}
	sort.Ints(n)

	ans := 0
	end := len(m) - K
	for i := 0; i < end; i++ {
		ans += n[i]
	}
	fmt.Println(ans)
}

Measured memory_bytes: 15488
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

int gcd(int x,int y){
  if(x%y==0) return y;
  else return gcd(y,x%y);
}

bool isPrime(int n){
  if(n < 2) return false;
  else if(n == 2) return true;
  else if(n%2==0) return false;

  for(int i=3;i<=sqrt(n);i++){
    if(n%i==0) return false;
  }
  return true;
}

int main(){
  ll n;
  ll ans = 0;
  cin >> n;
  vector<ll>A(n+1);
  vector<ll>B(n);
  for(int i=0;i<n+1;i++) cin >> A[i];
  for(int i=0;i<n;i++) cin >> B[i];

  for(int i=0;i<n;i++){
    if(A[i]>=B[i]) ans += B[i];
    else{
      ans += A[i]+min(A[i+1],B[i]-A[i]);;
      A[i+1] -= min(A[i+1],B[i]-A[i]);
    }
  }
  cout<< ans <<endl;
}


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

using namespace std;

int main(void)
{
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long tmp[4];
    tmp[0] = a*c;
    tmp[1] = a*d;
    tmp[2] = b*c;
    tmp[3] = b*d;
    long long ans = a*c;
    for (int i = 1; i < 4; i++) {
        if (ans < tmp[i]) {
            ans = tmp[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Xml;

class Program
{
	static void Main(string[] args)
	{
		long[] longArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
		long N = longArray[0];
		long K = longArray[1];
		N %= K;
		if (N > Math.Abs(N - K))
		{
			N = Math.Abs(N - K);
		}

		Console.WriteLine(N);
	}
}

//string s = Console.ReadLine();
//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = intArray[0];
//int W = intArray[1];
//int N = int.Parse(Console.ReadLine());
//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());
//Boolean ok = false;

//Console.WriteLine(ans);
//Console.WriteLine("Yes");
//Console.WriteLine("No");
//Console.ReadKey();

//string[] strArray = Console.ReadLine().Split(' ').ToArray();
//string S = strArray[0];
//string T = strArray[1];


Measured memory_bytes: 13396
S = input()

ans = 0
# 前の石の色
before_color = ''

for i, char in enumerate(S):
    if i == 0:
        before_color = char
        continue
    
    # 同じ石の場合は次へ
    if char == before_color:
        continue
    
    # 違う色の場合は1回回数増える
    ans += 1
    before_color = char
    
print(ans)

Measured memory_bytes: 39664
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;


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

	cin >> N;
	map<int, int>odd;
	map<int, int>even;
	for (int i = 0; i < N; i++) {
		cin >> M;
		if (i % 2)odd[M]++;
		else even[M]++;
	}
	long long int o = N;
	long long int oo = 0;
	long long int e = N;
	long long int ee = 0;
	for (auto i : odd) {
		if (N/2-i.second < o) {
			o = min(o, N / 2 - i.second);
			oo = i.first;
		}
	}
	for (auto i : even) {
		if (N/2-i.second < e) {
			e = min(e, N / 2 - i.second);
			ee = i.first;
		}
	}
	if (oo != ee) {
		cout << o + e << endl;
		return 0;
	}
	long long int ans = N;
	for (auto i : odd) {
		if (i.first != oo)ans = min(ans, e + N/2-i.second);
	}
	//cout << ans << endl;
	if (odd.size() == 1)ans = min(ans, e + N / 2);
	//cout << ans << endl;
	for (auto i : even) {
		if (i.first != ee)ans = min(ans, o + N/2-i.second);
	}
	//cout << ans << endl;
	if (even.size() == 1)ans = min(ans, o + N / 2);
	cout << ans << endl;
	return 0;
} 

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

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

    int prev = -999;
    for (int i = 0; i < N; i++) 
    {
        if (V[i]-1 >= prev) 
        {
            prev = V[i]-1;
        }
        else if (prev == V[i])
        {
            prev = V[i];
        }
        else 
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int num(string&s, int&i) {
	int n = 0;
	while (isdigit(s[i]))n = n * 10 + s[i++] - '0';
	return n;
}
P E[2][10000];
int v[2][10000];
int cnt;
int calc(string&s, int&i, int id) {
	int l = -1, r = -1;
	i++; if (s[i] == '(') { l = calc(s, i, id); i++; }
	int a = cnt++;
	i += 2; v[id][a] = num(s, i);
	i += 2; if (s[i] == '(') { r = calc(s, i, id); i++; }
	E[id][a].first = l; E[id][a].second = r;
	return a;
}
string dfs(int a, int b) {
	string s = ")[" + to_string(v[0][a] + v[1][b]) + "](";
	if (E[0][a].first != -1 && E[1][b].first != -1) {
		s = "(" + dfs(E[0][a].first, E[1][b].first) + s;
	}
	else s = "(" + s;
	if (E[0][a].second != -1 && E[1][b].second != -1) {
		s += dfs(E[0][a].second, E[1][b].second) + ")";
	}
	else s += ")";
	return s;
}
int main() {
	string a, b; cin >> a >> b;
	int r1, r2;
	int i = 0; r1 = calc(a, i, 0);
	i = 0; r2 = calc(b, i, 1);
	cout << dfs(r1, r2) << endl;
}

Measured memory_bytes: 3296
import qualified Data.Vector.Unboxed as V
import qualified Data.Map as MP
import Data.Tuple
import Data.Maybe
import Data.List

type Graph = MP.Map Int (V.Vector Int)

toTuple :: [Int] -> (Int, Int)
toTuple [a, b] = (a, b)

make :: Int -> Int -> V.Vector (Int, Int) -> Graph
make n m es = graph
    where
        init = V.foldl' (\g from -> MP.insert from (V.empty) g) MP.empty (V.fromList [1..n])
        graph = V.foldl' (\g (from, to) -> MP.adjust (V.cons to) from g) init (es V.++ V.map swap es)

solve :: Graph -> [Int] -> Int -> Int -> Int
solve graph arrived curr prev
   | curr `notElem` arrived = 0
   | null d = 1
   | otherwise = V.sum $ V.map (\n -> solve graph d n curr) ns
    where
       ns = V.filter (/=curr) $ fromJust $ MP.lookup curr graph
       d = delete curr arrived
        

main = do
    [n, m] <- map read . words <$> getLine :: IO [Int]
    es <- V.replicateM m (toTuple . map read . words <$> getLine)
    let graph = make n m es
    print $ solve graph [1..n] 1 (-1)

Measured memory_bytes: 1020
import java.util.Scanner;

public class Main {

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

        int a_count = scanner.nextInt();
        int[] a = new int[a_count + 1];
        for (int i = 0; i < a_count; i++) a[i] = scanner.nextInt();

        int b_count = scanner.nextInt();
        int[] b = new int[b_count];
        for (int i = 0; i < b_count; i++) b[i] = scanner.nextInt();

        int count = 0;
        for (int i = 0; i < b_count; i++) {
            a[a_count] = b[i];
            int j = 0;

            while (a[j] != b[i])
                j++;

            if (a_count != j)
                count++;
        }

        System.out.println(count);
    }

}



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

int main()
{
  int N, input;
  vector<int> A;
  cin >> N;
  for(int i=0;i<N - 1;i++){
    cin >> input;
    A.push_back(input);
  }
  sort(A.begin(),A.end());
  vector<int> ans(N,0);
  for(int i=0;i<N-1;i++){
    ans[A[i]-1]++;
  }
  for(int i=0;i<N;i++){
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 4988
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	string S;
  	string T;
  cin >> S ;
  
  if(S=="Sunny"){
    T="Cloudy";
  }else if(S=="Cloudy"){
  		T="Rainy";
  }else{
    	T="Sunny";
  }
  
  cout <<T << endl;
}



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

const int N = 3010;

ll dp[N][N][4];
int val[N][N];

void solve() {

    int r, c, k;
    scanf("%d%d%d", &r, &c, &k);
    for (int i = 1; i <= k; i++) {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        val[x][y] = v;
    }

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            for (int k = 0; k <= 3; k++) {
                dp[i][j][k] = max(dp[i-1][j][3], dp[i][j-1][k]);
            }
            for (int k = 1; k <= 3; k++) {
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][3]+val[i][j]);
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1]+val[i][j]);
                dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1]);
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= 3; i++) ans = max(ans, dp[r][c][i]);
    printf("%lld\n", ans);
}

int main() {
    int T = 1;
    // scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 321124
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

const int MAX = 200100;
ll fact[MAX], fact_inv[MAX];

ll power(ll a, ll b){
	ll res=1;
	while(b>0){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

ll comb(ll n, ll r){
	return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}

int main(){
	ll n, m, k;
	cin >> n >> m >> k;
	fact[0]=1;
	for( int i = 0; i < m*n+100; ++i ){
		fact[i+1]=fact[i]*(i+1)%MOD;
	}
	fact_inv[m*n+100]=power(fact[m*n+100], MOD-2);
	for( int i = m*n+99; i >= 0; --i ){
		fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
	}
	ll sum = 0;
	for( ll	d = 1; d < m; ++d ){
		sum += d*(n*n)*(m-d);
		sum %= MOD;
	}
	for( ll d = 1; d < n; ++d ){
		sum += d*(m*m)*(n-d);
		sum %= MOD;
	}
	cout << ( sum * comb(m*n-2, k-2) ) % MOD << endl; 
    return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>

int main(void)
{
        int ball[10];
        int i = 0, j = 0;
        int c = 0, b = 0;
        int n=0;


        scanf("%d",&n);
        for(j = 0; j < n; j++)
        {
                for(i = 0; i < 10; i++)
                {
                        ball[i] = 0;
                }
                for(i = 0; i < 10; i++)
                {
                        scanf("%d", &ball[i]);
                }
                for(i = 0; i < 10; i++)
                {
                        if( b < ball[i])
                        {
                                b = ball[i];
                                if(i == 9)
                                {
                                         printf("YES\n");
                                }
                        }
                        else if(c < ball[i] )
                        {
                                c = ball[i];
                                if(i == 9)
                                {
                                         printf("YES\n");
                                }
                        }
                        else
                        {
                                printf("NO\n");
                                break;
                        }
                }

                b = 0;
                c = 0;

        }
        return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long N, K;
  cin >> N >> K;
  vector<long long> neg, pos;
  long long zerocnt = 0;
  for (int i = 0; i < N; i++) {
    long long A;
    cin >> A;
    if (A < 0)
      neg.push_back(-A);
    else if (A > 0)
      pos.push_back(A);
    else {
      zerocnt++;
    }
  }
  sort(neg.begin(), neg.end());
  sort(pos.begin(), pos.end());
  if ((K -= 1ll * neg.size() * pos.size()) <= 0) {
    K = -K + 1;
    long long low = 0, high = 1ll << 60;
    while (high - low > 1) {
      long long mid = (high + low) / 2;
      long long cnt = 0;
      for (int i = 0; i < pos.size(); i++) {
        cnt += upper_bound(neg.begin(), neg.end(), mid / pos[i]) - neg.begin();
      }
      if (cnt < K) {
        low = mid;
      } else {
        high = mid;
      }
    }
    cout << -high << endl;
  } else if ((K -= zerocnt * (N - zerocnt) + zerocnt * (zerocnt - 1) / 2)
             <= 0) {
    cout << 0 << endl;
  } else {
    long long low = 0, high = 1ll << 60;
    while (high - low > 1) {
      long long mid = (high + low) / 2;
      long long cnt = 0;
      for (int i = 0; i < pos.size(); i++) {
        cnt += upper_bound(pos.begin(), pos.end(), mid / pos[i]) - pos.begin();
        if (pos[i] * pos[i] <= mid) cnt--;
      }
      for (int i = 0; i < neg.size(); i++) {
        cnt += upper_bound(neg.begin(), neg.end(), mid / neg[i]) - neg.begin();
        if (neg[i] * neg[i] <= mid) cnt--;
      }
      cnt /= 2;
      if (cnt < K) {
        low = mid;
      } else {
        high = mid;
      }
    }
    cout << high << endl;
  }
  return 0;
}


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

int main(){
  int d,n;
  cin>>d>>n;
  if(n==100){
    if(d<=1){
      cout<<101*pow(100,d)<<endl;
    }else{
      cout<<1010000<<endl;
    }
  }else{
    cout<<n*pow(100,d)<<endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){  
    int n,m,l;   
    scanf("%d %d %d",&n,&m,&l);  
    int A[n][m],B[m][l];  
    long long int C[n][l];  
for(int i = 0; i < n; i++){
    for(int j = 0; j < l; j++){ 
        C[i][j] = 0; 
          }    
}    
for(int i = 0; i < n; i++){ 
    for(int j = 0; j < m; j++){ 
        scanf("%d",&A[i][j]);
        } 
}   
for(int i = 0; i < m; i++){
    for(int j = 0; j < l; j++){ 
        scanf("%d",&B[i][j]); 
        }   
        }   
        for(int i = 0; i < n; i++){ 
            for(int k = 0; k < l; k++){ 
                for(int j = 0; j < m; j++){
                    C[i][k] += A[i][j]*B[j][k]; 
                } 
            }  
}   
for(int i = 0; i < n; i++){
    for(int j = 0; j < l-1; j++){ 
        printf("%lld ",C[i][j]);
        }
        printf("%lld\n",C[i][l-1]); 
        }
    return 0;
}



Measured memory_bytes: 2840
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define all(cont) cont.begin(), cont.end()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define fore(i,a,b) for(int i=a,almo5t=b;i<almo5t;++i)
#define SZ(x) ((int)x.size())
#define EPS 1e-9
#define PI acos(-1)
#define MOD 1000000007
#define FIN std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
const int N = 0;
 
typedef long long int ll;
typedef long double ld;
using namespace std;
 
int main(){
    FIN;
    //freopen("../input.txt", "r", stdin);

    ld a,b,H,M;cin>>a>>b>>H>>M;
    ld ang1 = (H*2*PI)/12 + (M*2*PI/60)/12;
    ld ang2 = (M*2*PI)/60;

    ld ang = ang1-ang2;
    ld ans = 0;
    //cout<<"ang = "<<(ang1*360)/(2*PI)<<"\n";
    //cout<<"ang = "<<(ang*360)/(2*PI)<<"\n";

    if(ans == 0){
        ans = sqrtl((a*a)+(b*b)-2*a*b*cosl(ang));
    }
    cout<<setprecision(10)<<ans<<"\n";
    //printf("%20.20Lf\n",ans);
    return 0;
}

// ============== Notes =============== //
// common bugs
// - remove reader 
// - fastio
// - int overflow (especially intermediate expressionns)
// - array bounds (indices bigger than MAXN?, is MAXN correct?)
// - special cases (n=1, graph not connected?)
// - re-initialize efficiently between test cases

Measured memory_bytes: 4064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int ans=n%10;
  if(ans==3){
    cout << "bon";
  }else if(ans==0 || ans==1 || ans==6 || ans==8){
    cout << "pon";
  }else{
    cout << "hon";
  }
}

Measured memory_bytes: 3636
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val a = (0 until n).map { sc.next().toInt() }
    println(problem081c(n, k, a))
}

fun problem081c(n: Int, k: Int, a: List<Int>): Int {
    val numbers = hashMapOf<Int, Int>()
    for (i in 0 until n) {
        if (!numbers.contains(a[i])) {
            numbers[a[i]] = 1
        } else {
            numbers[a[i]] = numbers[a[i]]!!.plus(1)
        }
    }
    val counts = numbers.values.sorted()
    var countsSize = counts.size
    if (numbers.size <= k) return 0
    var ans = 0
    for (i in counts.indices) {
        ans += counts[i]
        countsSize -= 1
        if (countsSize <= k) {
            return ans
        }
    }
    return ans
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    vector<int> v(3);
    v[0] = abs(a-b);
    v[1] = abs(b-c);
    v[2] = abs(c-a);
    sort(v.begin(),v.end());
    cout << v[0] + v[1] << endl;
}

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

int main(){
    ll x,y;
    cin>>x>>y;
    y/=x;
    int ans=0;
    while(y>=2){
        ans++;
        y/=2;
    }
    cout<<ans+1<<endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0003
{
    class Program
    {
        static void Main(string[] args)
        {
            // 与えられた2つの整数a,bの和の桁数を出力するプログラム

            string str;
            while ((str = Console.ReadLine()) != null)
            {
                int[] ary = str.Split(' ').Select(int.Parse).ToArray();
                int a = ary[0];
                int b = ary[1];
                Console.WriteLine((a + b).ToString().Length);
            }
        }
    }
}



Measured memory_bytes: 16212
# include <bits/stdc++.h>
# define ll long long int
# define ld long double
# define pb push_back
# define mp make_pair
# define mod 1000000007
# define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#else
// online submission
	#endif
	IOS
	int n;
	cin >> n;
	ll arr[n] = {0};
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	sort(arr, arr + n, greater<int>());
	ll sum = arr[0];
	for(int i = 1; i < n; i++){
		if((2*i) < n)
			sum += arr[i];
		if(2*i + 1 < n)
			sum += arr[i];
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 5180
$cnt = 0

def insertion_sort arr, size, distance
  # ??????g?????????????????????????????\???????????????
  # g?????????????±??????????????????????
  # 8 3 1 2 7 5 6 4
  # g = 4
  (distance..(size - 1)).each do |i|
    value = arr[i]
    last_target_index = i - distance
    while last_target_index >= 0 and arr[last_target_index] > value
      arr[last_target_index + distance] = arr[last_target_index]
      last_target_index = last_target_index - distance
      $cnt+=1
    end
    arr[last_target_index + distance] = value
  end
  arr
end

def shell_sort a, n
  g = get_m n
  m = g.size
  (0..(m - 1)).each {|i| insertion_sort a, n, g[i]}
  [m, g]
end

def get_m n
  result_array = [1]
  loop do
    next_pushed_value = (3 * result_array.last) + 1
    break if next_pushed_value > n
    result_array.push next_pushed_value
  end
  result_array.reverse
end


size = STDIN.gets.chomp.to_i
target_array = size.times.map{
  STDIN.gets.chomp.to_i
}
m, m_array = shell_sort(target_array, size)

puts m
puts m_array.join ' '
puts $cnt
target_array.each{|v| puts v}

Measured memory_bytes: 16724
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
#define REP(i,m,n) for(LL i=(m);i<(n);i++)

int main(){
  LL a,b;
  cin >> a >> b;
  
  if((a*b)%2 == 1){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3568
<?php
# 入力部
// fscanf(STDIN, "%d", $a);
// fscanf(STDIN, "%d %d", $a, $b);
// $s1 = fgets(STDIN); //"\n"の2文字
// $s2 = fgets(STDIN);
// fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%s", $s);
// fscanf(STDIN, "%s", $s2);

# 処理部
// $arr1 = str_split($s1);
// $arr2 = str_split($s2);
// $arr1 = explode(" ", $s1);
// $arr2 = explode(" ", $s2);
// for ($i = 0; $n > $x * $i; $i++) {
// }
// if (strpos($s, 'RRR') !== false) {
//   $r = 3;
// } elseif (strpos($s, 'RR') !== false) {
//   $r = 2;
// } elseif (strpos($s, 'R') !== false) {
//   $r = 1;
// } else {
//   $r = 0;
// }
// $s = "No";
// if ($x >= 30) {
//   $s = "Yes";
// }
// for ($i = 0; $i * 1000 < $n; $i++) {
// }
// $c = "a";
// if (ctype_upper($a)) {
//   $c = "A";
// }
// $s = "Yes";
// echo count($arr1);
// for ($i = 0; $i < strlen($s1); $i++) {
//   if ($arr1[$i] != $arr2[$i]) {
//     $s = "No";
//   }
// }
// $unit;
// switch ($n % 10) {
//   case 0:
//   case 1:
//   case 6:
//   case 8:
//     $unit = "pon";
//     break;
//   case 3:
//     $unit = "bon";
//     break;
//   default:
//     $unit = "hon";
//     break;
// }
if ($s == "ABC") {
  $r = "ARC";
} else {
  $r = "ABC";
}

# 出力部
echo $r . "\n";
// echo ($i * 1000) - $n . "\n";

Measured memory_bytes: 16088
/***
 ** " All that we are is the result of what we have thought. "
 ** 	-- Buddha
***/

/**
  *  Author: dhruv_gheewala
  *  Date:   29.03.2020
  *  Time:   03:09:17
**/

#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;

    #define p(str) 7
    #define o(str) 42
    #define fundri 108
    #define d(...) 1729
#endif


typedef unsigned int ui;
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

const bool testcases = 0;
#define ff first
#define ss second
#define endl '\n'
#define all(s) s.begin(),s.end()
#define test int __T__=1;if(testcases)cin>>__T__;while(__T__--)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define make_unique(vec) sort(all(vec));vec.erase(unique(all(vec)),vec.end())
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})

ll seed;auto random_address=[]{char *p=new char;delete p;return (uint64_t)p;};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()*(random_address()|1));
inline int rnd(int l=0,int r=INT_MAX){return uniform_int_distribution<int>(l,r)(rng);}

template<typename T>bool isPrime(T n){for(T i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
template<typename T>inline bool in_range(T a,T l,T r){return (a>=l&&a<=r);}

template<typename T,typename U>inline istream& operator >>(istream& in,pair<T,U> &a)
{in>>a.ff>>a.ss;return in;}
template<typename T>inline istream& operator >>(istream& in,vector<T> &a)
{for(auto &x : a)in>>x;return in;}
template<typename TAIL>inline void inp(TAIL& T){cin>>T;}
template<typename HEAD,typename... TAIL>inline void inp(HEAD &H,TAIL&... T){cin>>H;inp(T...);}

int main()
{
    std::chrono::time_point<std::chrono::high_resolution_clock> start_time, end_time;
    start_time = std::chrono::high_resolution_clock::now();

    #ifdef DHRUV_GHEEWALA
        freopen("INPUT.txt","r",stdin);
        freopen("OUTPUT.txt","w",stdout);
        freopen("DEBUG.txt","w",stderr);
    #endif
    
    fast;
    int x,y,a,b,c;
    test{

    inp(x,y,a,b,c);

    vi _p(a),q(b),r(c);

    inp(_p,q,r);
    sort(all(_p));
    sort(all(q));
    sort(all(r));

    multiset<int, greater<int> > appels;
    for(int i = a - 1; i >= a - x ; i--)
        appels.insert(_p[i]);

    for(int i = b - 1; i >= b - y ; i--)
        appels.insert(q[i]);

    int maxi = max(0, c - (x + y));
    for(int i = c - 1; i >= maxi; i--)
        appels.insert(r[i]);

    d(appels);
    ll ans = 0;
    for(int i = 0; i < x + y ; i++)
    {
        ans += *appels.begin();
        appels.erase(appels.begin());
    }

    cout<<ans<<endl;

    fundri;
    }

    end_time = std::chrono::high_resolution_clock::now();
    ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
    o("\n\n======\n");
    if(elapsed_time<10000)
        o("Elapsed Time: "<<elapsed_time<<" ms\n");
    else
        o("Elapsed Time: "<<elapsed_time/1000<<" s\n");

    return 0;
}

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

int main() {
  while (true) {
    int a, b;
    cin >> a >> b;
    if (a == 0 && b == 0) break;

    for (int i = 0; i < a; i ++) {
      if (i % 2 == 0) {
        for (int j = 0; j < b; j ++) {
          if (j % 2 == 0) cout << "#";
          else cout << ".";
        }
      } else {
        for (int j = 0; j < b; j ++) {
          if (j % 2 == 0) cout << ".";
          else cout << "#";
        }
      }
      cout << endl;
    }
    cout << endl;
  }
}



Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int si=s.size(),count=0;
    rep(i,si/2){
        if(s[i]!=s[si-i-1]){
            count++;
        }
    }
    cout<<count<<'\n';
    return(0);
}

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

int main(){
	int N,M;
	cin>>N>>M;
	int ac=0;
	int pena=0;
	vector<bool> pro1(N,false);//ACしてるか　と　WAの回数
	vector<int> pro2(N,0);
	int p;
	string S;
	for(int i=0;i<M;i++){
		cin>>p>>S; p--;
		if(S=="AC")pro1[p]=true;
		if(pro1[p]==false && S=="WA")pro2[p]++;
	}
	for(int i=0;i<N;i++){
		if(pro1[i]){
			ac++;
			pena+=pro2[i];
		}
		// cout<<(pro1[i] ? "AC" : "WA")<<' '<<pro2[i]<<endl;
	}
	
	cout<<ac<<" "<<pena<<endl;
}



Measured memory_bytes: 640
#include <iostream>
#include <cstdio>

using namespace std;

int n;
int a[200005];
int b[128];
int d[200005];
string s;
char c[200005];

int main()
{
    cin>>s;
    n = s.size();
    s = '.' + s;
    for(char i = 'a'; i <= 'z'; i++)
    {
        b[i] = n + 1;
    }
    for(int i = n; i >= 0; i--)
    {
        char mj;
        int mn = 1e9;
        for(char j = 'a'; j <= 'z'; j++)
        {
            if(a[b[j]] < mn)
            {
                mn = a[b[j]];
                mj = j;
            }
        }
        a[i] = mn + 1;
        c[i] = mj;
        d[i] = b[mj];
        b[s[i]] = i;
    }
    int now = 0;
    while(a[now] != 0)
    {
        putchar(c[now]);
        now = d[now];
    }
    return 0;
}


Measured memory_bytes: 2368
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
typedef queue<ll> qll;
typedef queue<pll> qp;
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(ll i = ll(a - 1); i >= ll(b); i--)
#define rev(...) _overload3(__VA_ARGS__, revi, _rev,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll factorial(ll a){return a < 2 ? 1 : factorial(a - 1) * a;}
ll summation(ll a){return a < 1 ? 0 : (a * a + a) / 2;}
const ll INF = 1e16, MOD = 1e9 + 7;
const string ALPHABETS = "abcdefghijklmnopqrstuvwxyz";
ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
//ll dx[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll N, M, X, Y, Z, W, H;
string S, T;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> S){
        ll res = 0, g_cnt = 0, p_cnt = 0, mx = -INF, mn = INF, a[] = {}, b[] = {}, c[] = {};
        bool flag = true;
        vll v;
        pll p;
        qll q;
        each(c, S){
            if(c == 'g'){
                if(p_cnt < g_cnt){
                    res++, p_cnt++;
                }else{
                    g_cnt++;
                }
            }else{
                if(p_cnt < g_cnt){
                    p_cnt++;
                }else{
                    res--, g_cnt++;
                }
            }
        }
        print(res);
    }
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	
	ll n,k;
	cin >> n >> k;
	
	vector<ll> v;
	
	for(int i=0;i<n;i++){
		
		ll x; cin >> x;
		
		v.push_back(x);
		
	}
	
	sort(v.begin(),v.end());
	
	ll ans = 1e18;
	
    for(int i=0;i+k<=n;i++){
    
      	ll  l = -v[i];
      	  
    	ll  r = v[i+k-1];
    	
    	ans = min(ans,l+r+min(abs(l),abs(r)));

	}

    cout << ans << endl;
    
	return 0;
}


Measured memory_bytes: 1400
import java.util.*;

public class Main {
    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);
        // 整数の入力
        // final int a = sc.nextInt();
        // 文字列の入力
        // final String s1 = sc.next();
        final int varN = Integer.parseInt(sc.next());
        int mod = 1000000007;

        long result = 0;
        long p = 0;
        long cur = 0;
        for (int i = 0; i < varN; i++) {
            cur = Long.parseLong(sc.next());
            result = (result + (cur * p) % mod) % mod;
            p = (cur + p) % mod;
        }
        sc.close();
        System.out.println(result);
    }
}


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	string s;cin >> s;
	
	int r = 0;
	int b = 0;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '0'){
			r++;
		}else{
			b++;
		}
	}

	cout << min(r,b)*2 << endl;

	return 0;
}


Measured memory_bytes: 3760
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define qwq(x) cerr<<"# "<<#x<<" = "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long u64;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int T=10,S=(2<<T)+5,N=105,mod=998244353;
int f[S],g[N][N],h[N],a[N],n;
unordered_map<u64,int> F;
char s[N];

int fix(int x){
	return x>=mod?x-mod:x;
}

int solve(u64 s,int n){
	if(n<=1)return (s&1)+1;
	if(n<=T&&f[s|(1<<n)])return f[s|(1<<n)];
	if(n>T&&F.count(s|(1ll<<n)))return F[s|(1ll<<n)];	
	int res=solve(s>>1,n-1);
	if(s&1)res=fix(res+res);
	int suf[n+1];
	fill(suf,suf+n+1,-1);
	rep(len,1,n/2){
		u64 st=(1ll<<len)-1,las=-1; int ans=0;
		for(int p=0,k=1;p+len<=n;p+=len,k++){
			st&=s>>p;
			if(k>=2){
				if(st!=las)ans=solve(st,len);
				if(suf[p+len]==-1)
					suf[p+len]=solve(s>>(p+len),n-p-len);
				las=st,res=(res+(ll)ans*suf[p+len])%mod;
			}
		}
	}
	if(n<=T)f[s|(1<<n)]=res;
	else F[s|(1ll<<n)]=res;
	return res;
}

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	rep(i,1,n)a[i]=s[i]-'0',g[i][i]=a[i]+1;
	rep(len,1,n/2)
		rep(l,1,n-2*len+1){
			u64 full=(1ll<<len)-1,st=(1ll<<len)-1,las=-1; int ans=0;
			for(int p=l,k=1;p+len<=n+1;p+=len,k++){
				REP(i,len)st&=full-(1ll<<i)+((1ll*a[p+i])<<i);
				if(k>=2){
					if(st!=las)ans=solve(st,len);
					las=st,g[l][p+len-1]=fix(g[l][p+len-1]+ans);
				}
			}
		}
	h[0]=1;
	rep(i,1,n)rep(j,0,i-1)
		h[i]=(h[i]+(ll)h[j]*g[j+1][i])%mod;
	cout<<h[n]<<endl;
	return 0;
}

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

long long FPB(long long x,long long y){
	if(y==0){
		return x;
	}
	else{
		return FPB(y,x%y);
	}
}

int main(){
	long long a,b,x,y;
	long long i=1;
	long long itung=0;
  cin >> a >> b >> x >> y;
  
  long long cari_x=(b/x)-((a-1)/x);
  long long cari_y=(b/y)-((a-1)/y);
  long long xx=((b-a)+1)-(cari_x+cari_y);
  
	long long FPB_2=FPB(x,y);
	
	long long KPK=FPB_2*((x/FPB_2))*((y/FPB_2));

//	while(KPK*i>=a && KPK*i<=b){
//		if(KPK*i<=b && KPK*i>=a){
//			itung++;
//		}
//		i++;
//	}
	
	itung=(b/KPK)-((a-1)/KPK);

	cout << xx+itung << endl;
	

}




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

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	bool flag = false;
	int old = a % b;
	int now;
	if(old == c) flag = true;
	while(1){
		now = (old + a) % b;
		if(now == c) flag = true;
		if(now == c || now == a % b) break;
		old = now;
	}
	if(flag) cout << "YES" << endl;
	else cout << "NO" << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int n,a,b;

int main(){
	cin>>n;
	while(cin>>a>>b){
		if(a<=5||a>5&&b>a){
			if(a<b){
				for(int i=a;i<=b;i++){cout<<i;if(i!=b)cout<<" ";}
				cout<<endl;
			}
			else {
				for(int i=a;i>=b;i--){cout<<i;if(i!=b)cout<<" ";}
				cout<<endl;
			}
		}
		if(a>5&&b<=5){
			for(int i=a;i<=9;i++)cout<<i<<" ";
			for(int i=5;i>=b;i--){cout<<i;if(i!=b)cout<<" ";}
			cout<<endl;
		}
		if(a>5&&b>5&&b<a){
			for(int i=a;i<=9;i++)cout<<i<<" ";
			cout<<"5 4 3 2 1 0 1 2 3 4 5 ";
			for(int i=6;i<=b;i++){cout<<i;if(i!=b)cout<<" ";}
			cout<<endl;
		}
	}
}

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

using namespace std;

int main(){
    int n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    string s;
    cin>>s;
    if(s[c-1]=='#'||s[d-1]=='#'){
        cout<<"No"<<endl;
        return 0;
    }
    if(c<d){
        //b->d
        int p=b-1;
        while(p!=d-1&&p<n-1){
            if(s[p+1]!='#')++p;
            else if(p+2<=n-1&&s[p+2]!='#')p+=2;
            else {
                cout<<"No"<<endl;
                return 0;
            }
        }
        if(p>=n){
            cout<<"No"<<endl;
            return 0;
        }
        //a->c
        p=a-1;
        while(p!=c-1&&p<n-1){
            if(s[p+1]!='#')++p;
            else if(p+2<=n-1&&s[p+2]!='#')p+=2;
            else {
                cout<<"No"<<endl;
                return 0;
            }
        }
        if(p>=n){
            cout<<"No"<<endl;
            return 0;
        }
    }
    else{//[a-[b-d]-c]
        int p=a-1,q=b-1;
        while(p!=c-1||q!=d-1){
            if(p>=n||q>=n){
                cout<<"No"<<endl;
                return 0;
            }
            if(p!=c-1){//aを優先的に動かす
                if(s[p+1]!='#'&&p+1!=q)++p;
                else if(p+2<=n-1&&s[p+2]!='#'&&p+2!=q)p+=2;
                else{//bを動かす必要性
                    if(s[q+1]!='#')++q;
                    else if(q+2<=n-1&&s[q+2]!='#')q+=2;
                    else {
                        cout<<"No"<<endl;
                        return 0;
                    }
                }
            }
            else{
                if(s[q+1]!='#')++q;
                else if(q+2<=n-1&&s[q+2]!='#')q+=2;
                else {
                    cout<<"No"<<endl;
                    return 0;
                }
            }
        }

    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
typedef long long ll;
#define vint vector<int>
#define vstring vector<string>

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << (double)a*(double)b/2 << ' ';
    if (a%2 == 0 && b%2 == 0){
      if(a/2 == c && b/2 == d) cout << "1" << endl;
      else cout << "0" << endl;
    }
    else 
      cout << "0" << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
int main(){
	string s;
	cin>>s;
	ll cur = 0,p = 1,ans = 0;
	ll cnt[2020] = {0};
	cnt[0] = 1;
	int len = s.length() - 1;
	for(int i = len ;i>=0;i--){
		cur = (cur + (ll)(s[i]-'0')*p)%2019;
		ans+=cnt[cur]++;
		p = p*10%2019;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3740
n = int(input())
cnt = 1
break_cnt = 0
input_brick = map(int, input().split(' '))
flag = False
for i in input_brick:
    if i == 1:
        flag = True
    if cnt == i:
        cnt += 1
        continue
    break_cnt += 1
if flag:
    print(break_cnt)
else:
    print('-1')

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


int main(){
    unsigned long long N,point=0,count=1;
    unsigned long long sum=0;
    cin >> N;
    vector<char> a(10);//長さ10文字の文字列をソートするためのchar
    vector<string> str(N);//文字列をソートする
    for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            cin >> a.at(j);//1文字ずつ受け取る
        }
        sort(a.begin(),a.end());//文字列のソート
        for(int j=0;j<10;j++){
            str.at(i) += a.at(j);//10個の文字を文字列へ
        }
    }

    sort(str.begin(),str.end());//文字列の集合のソート

    for(int i=1;i<N;i++){
        if(str.at(point)==str.at(i)) {//文字列が一致したら加算へ
            count++;
        }else {
            point = i;
            sum += count*(count-1)/2;//nC2で加算
            count=1;//
        }
    }
    
    sum += count*(count-1)/2;
    cout<< sum << endl;
}

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

int main() {
	list <char> ls;		string s;	cin >> s;
	int n = s.length();
	loop (i, n)		ls.push_back(s[i]);
	int q;	cin >> q;
	bool rev = 0;
	for (int i = 0; i < q; i++) {
		int x, y;	char temp;		cin >> x;	--x;
		if (!x)		rev ^= 1;
		else {
			cin >> y >> temp;	y--;
			if (!(y ^ rev))		ls.push_front(temp);
			else	ls.push_back(temp);
		}
	}
	if (rev)	reverse(ls.begin(), ls.end());
	for (auto i : ls)	cout << i;
	cout << endl;
	return 0;
}

Measured memory_bytes: 9984