akhauriyash/Code-Regression huggingface dataset:
// #define STOPIT
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

void debug_impl() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
    #define debug(...)\
    do {\
        cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
        debug_impl(__VA_ARGS__);\
        cerr << std::noboolalpha;\
    } while (false)
#else
    #define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr>
istream& operator>> (istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr >
ostream& operator<< (ostream& os, Container const& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

char simulation(const string &s, vector<pair<char, char>> magics, int pos)
{
    if (s.size()<=pos) return 'R';
    if (pos<0) return 'L';

    for (auto magic: magics)
    {
        if (s[pos] == magic.first)
        {
            if (magic.second == 'L')
                --pos;
            else
                ++pos;

            if (pos == s.size()) return 'R';
            if (pos == -1) return 'L';
        }
    }
    return 'C';
}

int main()
{
    int n, q;
    cin >> n >> q;
    if (n == 0)
        return 0;

    string s;
    cin >> s;

    vector<pair<char, char>> magics(q);
    rep(i, 0, q)
        cin >> magics[i].first >> magics[i].second;

    int cnt = 0;
    // count gollems who will fall into right side
    {
        int left = 0;
        int right = n;
        while (left<right)
        {
            int center = (left+right)>>1;

            char result = simulation(s, magics, center);
            if (result == 'C' or result == 'L')
                left = center+1;
            else
                right = center;
        }
        cnt += n-left;
    }

    // count gollems who will fall into left side
    {
        int left = -1;
        int right = n-1;
        while (left<right)
        {
            int center = (left+right+1)>>1;

            char result = simulation(s, magics, center);
            if (result == 'C' or result == 'R')
                right = center-1;
            else
                left = center;
        }
        cnt += left+1;
    }
    
    cout << n - cnt << endl;
    return 0;
}


Measured memory_bytes: 1284
function Main(input){
  input = input.split("\n");
  inputStr = input[0].split(" ");
  var N = Number.parseInt(inputStr[0]);
  var M = Number.parseInt(inputStr[1]);
  var C = Number.parseInt(inputStr[2]);
  var B_array = input[1].split(" ");
  var A_array = [];
  var tmp = 0;
  var cnt = 0;
  
  for(var i1=0; i1<N ; i1++){
	A_array = input[i1+2].split(" ");
    //console.log(A_array);
    tmp = 0;
    for( var i2=0; i2<M ; i2++){
		tmp += Number.parseInt(B_array[i2]) * Number.parseInt(A_array[i2]);
      	//console.log(tmp);
    }
    if ( tmp + C > 0 ){
      cnt += 1;
    }
  }
  //結果の出力
  console.log(cnt);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));



Measured memory_bytes: 7372
// 20:58 -
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <stack>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

/* エラトステネスの篩 */
const int MAX = 100005;
bool prime[MAX+1];
void make_prime() {
      for(int i = 0; i  <= MAX; i++ )
            prime[i] = true;
      prime[1] = false;
      for(int p = 2; p <= MAX; p++ ) // 表だけ作るなら p*p <= MAXでもOK
            if(prime[p])  // pが素数なら
                 for(int n = p+p; n <= MAX; n += p)  // pの倍数は素数でない
                       prime[n] = false;
}
int cnt[MAX+1] = {0};
// 累積和
void cal(){
  for(int i = 1; i <= MAX; i++){
    cnt[i] = cnt[i-1];
    if(prime[i] && prime[(i+1)/2]){
      cnt[i] = cnt[i-1] + 1;
    }
  }
}

int main(){
  int l, r;
  int Q;

  make_prime();
  cal();

  cin >> Q;
  for(int i = 0; i < Q; i++){
    cin >> l >> r;
    /*for(int k = l; k < r; k++){
      cout << "k:" << k << " " << prime[k] << endl;
      cout << "cnt:" << cnt[k] << endl;
    }*/
    cout << cnt[r] - cnt[l-1] << endl;
  }

  return 0;
}


Measured memory_bytes: 1152
H, W = gets.split(' ').map(&:to_i)
c = []
10.times do |i|
  c << gets.split(' ').map(&:to_i)
end
A = []
H.times do |h|
  A << gets.split(' ').map(&:to_i)
end

10.times do |k|
  10.times do |i|
    10.times do |j|
      c[i][j] = [c[i][j], c[i][k] + c[k][j]].min
    end
  end
end

sum = 0
A.flatten.delete_if{|n| n < 0}.map{|n|c[n][1]}.each{|n| sum += n}
puts sum





Measured memory_bytes: 3324
#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(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL 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 inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(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  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
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; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
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; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

LL n, k, a[200000], b[200000];

bool f(LL v) {
	LL c = 0;
	inc(i, n) { c += max(0LL, a[i] - v / b[i]); }
	return (c <= k);
}

int main() {
	cin >> n >> k;
	inc(i, n) { cin >> a[i]; }
	inc(i, n) { cin >> b[i]; }
	
	sort(a, a + n);
	sort(b, b + n, greater<LL>());
	
	LL L = -1, H = 1e12 + 1;
	while(H - L > 1) {
		LL M = (L + H) / 2;
		(f(M) ? H : L) = M;
	}
	
	cout << H << endl;
	
	return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(string s,char c){
    if(s.length()==n){
        cout<<s<<endl;
        return ;
    }
    for(char chr='a';chr<=c+1;++chr){
        dfs(s+chr,max(c,chr));
    }
}

int main(){
    cin>>n;
    dfs("a",'a');
    return 0;
}

Measured memory_bytes: 1536
N,M=map(int,input().split())
X=list(map(int,input().split()))
if N>=M:
    print(0)
else:
    X.sort()
    sa=[X[i+1]-X[i] for i in range(M-1)]
    sa.sort()
    res=0
    for i in range(1,N):
        res+=sa[-i]
    print(sum(sa)-res)

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


int main(){
    int h, n, sum = 0;
    cin >> h >> n;
    for (int i=0; i<n; i++){
        int a;
        cin >> a;
        sum += a;
    }

    if (h <= sum){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    

    return 0;
}


Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let k: usize = iterator.next().unwrap().parse().unwrap();
    let r: usize = iterator.next().unwrap().parse().unwrap();
    let s: usize = iterator.next().unwrap().parse().unwrap();
    let p: usize = iterator.next().unwrap().parse().unwrap();

    let mut t: Vec<char> = iterator.next().unwrap().chars().collect();
    let mut ans = 0;

    for i in 0..n {
        if i >= k && t[i] == t[i - k] {
            t[i] = 'x';
        } else {
            let hand = t[i];
            if hand == 'r' {
                ans += p;
            } else if hand == 's' {
                ans += r;
            } else if hand == 'p' {
                ans += s;
            }
        }
    }

    return ans.to_string();
}


Measured memory_bytes: 4352
/*input
3 1
1 2
1 3
2 3
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i, j, k)  for(int i = j; i <  k; ++i)
#define RREP(i, j, k) for(int i = j; i >= k; --i)
#define F first
#define S second
#define mp make_pair
#define pb emplace_back
#define PII pair<int , int>
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 100009
#define INF 0x3f3f3f3f

int n , m , dp[MAX] , o[MAX] , p[MAX];
vector<int> v[MAX] , g[MAX];
int DFS1(int now){
    if(dp[now] != 0) return dp[now];
    dp[now] = 1;
    for(auto to : v[now]) dp[now] = max(dp[now] , DFS1(to) + 1);
    return dp[now];
}

int32_t main(){
    IOS;
    cin >> n >> m;
    REP(i , 1 , n - 1 + m + 1){
        int a , b;
        cin >> a >> b;
        v[a].pb(b);
        g[b].pb(a);
        o[b] = 1;
    }  
    int root = 1;
    REP(i , 1 , n + 1) if(o[i] == 0) root = i;
    DFS1(root);
    // REP(i , 1 , n + 1) cout << dp[i] << " "; cout << endl;
    REP(i , 1 , n + 1){
        int big = INF;
        for(auto to : g[i]) big = min(big , dp[to]);
        for(auto to : g[i]) if(big == dp[to]) p[i] = to;
    }
    REP(i , 1 , n + 1) cout << p[i] << endl;
    return 0;
}

Measured memory_bytes: 16128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int count = 0;
		for (int i = 0; i < n; i++) {

			int a = sc.nextInt();
			int b = sc.nextInt();

			if (a == b) {
				count++;
			} else {
				count = 0;
			}

			if (count == 3) {
				System.out.println("Yes");
				return;
			}

		}
		System.out.println("No");
	}
}

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

dpx=[[0 for i in range(0,N)] for i in range(0,N+1)]
dpy=[[0 for i in range(0,N)] for i in range(0,N+1)]

for i in range(1,N+1):
    for j in range(0,N):
        if N>j+i-1 and i!=1:
            dpx[i][j]=max(dpy[i-1][j+1]+A[j],dpy[i-1][j]+A[j+i-1])
            dpy[i][j]=min(dpx[i-1][j+1]-A[j],dpx[i-1][j]-A[j+i-1])
        elif N>j+i-1 and i==1:
            dpx[i][j]=A[j]
            dpy[i][j]=-A[j]

print(dpx[N][0])

Measured memory_bytes: 192008
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h,w;

        while(true){
            h=sc.nextInt();
            w=sc.nextInt();
            if(h==0 && w==0){
                break;
            }
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if((i%2==0 && j%2==0) || (i%2==1 && j%2==1)){
                        System.out.print("#");
                    }else{
                        System.out.print(".");
                    }
                }
                System.out.print("\n");
            }
            System.out.print("\n");
        }

        sc.close();
    }
}



Measured memory_bytes: 37764
#include<iostream>
#include<algorithm>
#define MAX 100001
using namespace std;
void print(int n,int A[MAX],int standard){
    for(int i=0;i<n;i++){
        if(i>0){
            cout << ' ';
        }
        if(i==standard){
            cout << '[' << A[i] << ']';
        }else{
            cout << A[i];
        }
    }
    cout << endl;
}
int partition(int n,int A[MAX],int r){
    int standard = A[r];
    int wall = 0;
    for(int i=0;i<n-1;i++){
        if(A[i] <= A[r]){
            wall++;
            swap(A[wall-1],A[i]);
        }
    }
    swap(A[r],A[wall]);
    return wall;
}
int main(void){
    int n,A[MAX],standard;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    standard = partition(n,A,n-1);
    print(n,A,standard);
    return 0;
}


Measured memory_bytes: 3456
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn convert2usize(substr: &str) -> usize {
    substr.parse::<usize>().unwrap()
}

fn main() {
    let mut target = get_line();
    let n = get_line().parse::<usize>().unwrap();

    for _ in 0..n {
        let line = get_line();
        let operations = line.split_whitespace().collect::<Vec<&str>>();
        let (start, end) = (convert2usize(operations[1]), convert2usize(operations[2]) + 1);
        let copy = target.clone();
        match operations[0] {
            "print" => println!("{}", &target[start..end]),
            "reverse" => {
                let s0 = &copy[..start];
                let s2 = &copy[end..];
                let s1 = &copy[start..end].chars().rev().collect::<String>();
                target = format!("{}{}{}", s0, s1, s2);
            },
            "replace" => {
                let s0 = &copy[..start];
                let s2 = &copy[end..];
                target = format!("{}{}{}", s0, operations[3], s2);
            },
            _ => {},
        }
    }
}



Measured memory_bytes: 5036
"use strict";

const main = arg => {
    const input = arg.trim().split("\n");
    const n = Number(input[0])
    const as = input[1].split(" ").map(el => parseInt(el))
    let arr = new Array(n).fill(0)
    for(let a of as){
        arr[a-1] = arr[a-1] + 1
    }
    let res = arr.join('\n')
    console.log(res)

}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  



Measured memory_bytes: 60508
s = input()
bl = True
for i in range(len(s)):
    if i == 0:
        if s[i] != "A":
            print("WA")
            exit()
    elif 2 <= i <= len(s) - 2:
        if s[i] == "C" and bl:
            bl = False
        else:
            if not s[i].islower():
                print("WA")
                exit()
    else:
        if not s[i].islower():
            print("WA")
            exit()
if not bl:
    print("AC")
else:
    print("WA")



Measured memory_bytes: 3064
import java.util.*;

public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}
	public Main() {
		new AOJ0240();
	}
	
	class AOJ0240{
		int n,y;
		int doIt(){
			int result = 0;
			
			
			
			return result;
		}
		
		
		public AOJ0240() {
			while(true){
				n = in.nextInt();
				if(n==0)break;
				y = in.nextInt();
				ArrayList<Bank> list = new ArrayList<Bank>();
				for(int i=0;i<n;i++)list.add(new Bank(in.nextInt(), in.nextInt(), in.nextInt()));
				int result = 0;
				double max = Integer.MIN_VALUE;
				for(int i=0;i<n;i++)if(list.get(i).sum>max){
					max = list.get(i).sum;
					result = list.get(i).ban;
				}
//				for(int i=0;i<n;i++)System.out.println(list.get(i).ban+" "+list.get(i).sum);
				System.out.println(result);
			}
		}
		
		class Bank{
			int ban,syu,ritu;
			double sum;
			public Bank(int ban,int ritu,int syu) {
				this.ban = ban;
				this.syu = syu;
				this.ritu = ritu;
				if(syu==1){
					this.sum = (double)(1+y*(1.0*ritu/100));
				}
				else{
					this.sum = (double)(Math.pow(1+(1.0*ritu/100), y));
				}
			}
		}
	}

}

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

// ------------------------

void solve() {
    int N; cin >> N;
    int K; cin >> K;
    vector<ll> H(N); rep(i, N) cin >> H[i];
    if(N <= K){
        cout << 0 << "\n";
        return;
    }else{
        sort(H.begin(), H.end());
        ll sum = 0;
        int itr = 0;
        for( auto & v : H ){
            if(itr == N-K)break;
            sum += v;
            ++itr;
        }
        // ll tmp = accumulate(H.begin(), H.end()-K, 0);
        cout << sum << "\n";
    }
    return;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>

int main(){
  int i, j, temp, count = 0, n, *array;
  
  scanf("%d",&n);
  array = (int *)malloc(n * sizeof(int));
  for(i = 0; i < n; i++){
    scanf("%d",&array[i]);
  }
  for(i = 0; i < n - 1; i++){
    for(j = n - 1; j > i; j--){
      if(array[j - 1] > array[j]){
	temp = array[j - 1];
	array[j - 1] = array[j];
	array[j] = temp;
	count++;
      }
    }
  }
  for(i = 0; i < n - 1; i++){
    printf("%d ",array[i]);
  }
  printf("%d\n",array[n - 1]);
  printf("%d\n",count);
  
  return 0;
}



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


public class Main {
	public static void main(String[] args) {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Scanner scan=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		
		int x=scan.nextInt();
		int y=scan.nextInt();
		int z=scan.nextInt();
		int c=0;
		for (int i = x; i <= y; i++) {
			if(z%i==0)
				c++;
		}
		System.out.println(c);
		
	}

}

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

int main()
{

        long long N, A, B;
        cin >> N >> A >> B;


        long long total = A + B;

        long long amari = N % total;

        long long sho = N / total;

        long long num = sho * A;

        if (amari < A) {
                num += amari;
        }
        else {
                num += A;
        }
        cout << num << endl;



}


Measured memory_bytes: 256
//abc116_a.cpp
//Sat Feb  2 16:59:04 2019

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

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

	cout << a*b/2<< endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n;
string t;
char c[200];
vector<int> vec1, vec2;

signed main() {
	cin >> n;
	cout << "? ";
	for (int i = 1; i <= n; i++)cout << i << " ";
	cout << endl;
	cin >> t;
	int mi = 1, ma = n + 1;
	while (ma - mi > 1) {
		int md = (mi + ma) / 2;
		cout << "? ";
		for (int i = md; i < md + n; i++)cout << i << " ";
		cout << endl;
		string s; cin >> s;
		if (s == t)mi = md;
		else ma = md;
	}
	if (t == "Red")c[mi] = 'R', c[mi + n] = 'B';
	else c[mi] = 'B', c[mi + n] = 'R';
	for (int i = 1; i < mi; i++) {
		cout << "? " << i << " ";
		for (int j = ma; j < mi + n; j++)cout << j << " ";
		cout << endl;
		string s; cin >> s;
		if (s == "Red")c[i] = 'R', vec1.push_back(i);
		else c[i] = 'B', vec2.push_back(i);
	}
	for (int i = ma + n; i <= 2 * n; i++) {
		cout << "? " << i << " ";
		for (int j = ma; j < mi + n; j++)cout << j << " ";
		cout << endl;
		string s; cin >> s;
		if (s == "Red")c[i] = 'R', vec1.push_back(i);
		else c[i] = 'B', vec2.push_back(i);
	}
	for (int i = ma; i < mi + n; i++) {
		cout << "? ";
		for (int j = 0; j < n / 2; j++)cout << vec1[j] << " ";
		for (int j = 0; j < n / 2; j++)cout << vec2[j] << " ";
		cout << i << " " << endl;
		string s; cin >> s;
		if (s == "Red")c[i] = 'R';
		else c[i] = 'B';
	}
	cout << "! ";
	for (int i = 1; i <= n * 2; i++)cout << c[i];
	cout << endl;
}


Measured memory_bytes: 724
//============================================================================
// Name        : PetrozavodskContest001.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : atcorder Petrozavodsk Contest 001 in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

inline int main001();

int main() {
	main001();

	return 0;
}

inline int main001() {

	int x, y, i;

	cin >> x >> y;

	if (x % y == 0) {
		cout << -1;
	} else {
		i = 1;

		while (((x * ++i) % y) == 0)
			;

		cout << x * i;
	}

	return 0;

}


Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N, C;
int D[50][50], c[510][510], cost[50][3];
 
signed main() {
    cin >> N >> C;
    for(int i=0; i<C; i++) {
        for(int j=0; j<C; j++) {
            cin >> D[i][j];
        }
    }
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> c[i][j]; c[i][j]--;
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            int mod3 = (i + j) % 3;
            for(int col=0; col<C; col++) {
                cost[col][mod3] += D[ c[i][j] ][col];
            }
        }
    }

    int ans = INF;
    for(int i=0; i<C; i++) {
        for(int j=0; j<C; j++) {
            for(int k=0; k<C; k++) {
                if(i == j or j == k or k == i) continue;
                int tmp = cost[i][0] + cost[j][1] + cost[k][2];
                chmin(ans, tmp);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    ll h, w, n;
    cin >> h >> w >> n;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];
    int inc = 1;
    ll nh = 0, nw = 0;
    ll tmp = 0;
    vector<vector<ll>> ans(h, vector<ll>(w));
    rep(i, 0, n) {
        ll tmp = 0;
        while(tmp < a[i]){
            ans[nh][nw] = i+1;
            if(inc) {
                if(nw == w-1) {
                    nh++;
                    inc = 0;
                }else{
                    nw++;
                }
            } else {
                if(nw == 0) {
                    nh++;
                    inc = 1;
                } else {
                    nw--;
                }
            }
            tmp++;
        }
    }
    rep(i, 0, h) rep(j, 0, w) cout << ans[i][j] << (j == w-1 ? "\n" : " "); 
    return 0;
}

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

int main()
{
	int x;
	cin >> x;
	int t;
	for (t=1; t < x; ++t) {
		if (t * (t+1) / 2 >= x) {
			break;
		}
	}
	cout << t;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    int a[10004];
    int i;
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int ans = 0;
    for (i = 0; i < n; i++)
    {
        while (a[i] % 2 == 0)
        {
            ans++;
            a[i] /= 2;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
n, y = gets.chomp.split(" ").map(&:to_i)
result = ""
exit_flag = false
(0..n).each do |i|
  (0..n-i).each do |j|
    k = n-i-j
    sum = 10000 * i + 5000 * j + 1000 * k
    if sum == y
      puts("#{i} #{j} #{k}")
      exit_flag = true
      break
    end
  end
  if exit_flag
    break
  end
end
if exit_flag == false
  puts("-1 -1 -1")
end

Measured memory_bytes: 1788
import java.util.Scanner;

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

        int res = 0;
        for(int i = 1; i < N+1; i++) {
            int v = sc.nextInt();
            if(i%2!=0 && v%2!=0) res++;
        }
        System.out.println(res);
    }
}


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

int main()
{
    string s,t;
    cin >> s;
    cin >> t;
    ll ns = s.size();
    ll nt = t.size();
    if(ns > nt) cout << "GREATER" << endl;
    else if(nt > ns)cout << "LESS" << endl;
    else{
        for(ll i = 0;i < ns;i++){
            if(s[i] > t[i]){
                cout << "GREATER" << endl;
                return 0;
            } else if(s[i] < t[i]){
                cout << "LESS" << endl;
                return 0;
            }
        }
        cout << "EQUAL" << endl;
    }
}


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

using namespace std;

int count75(int prev, const std::vector<int>& counts, int const startIdx) {
  int const count = counts[startIdx];
  if (count == 0) {
    return prev == 75 ? 1 : 0;
  }
  int ret = 0;
  for (int i = 1; i <= std::min(count + 1, 75); i += 2) {
    if (i % 7 == 0 || i % 9 == 0 || i % 11 == 0 || i % 13 == 0 || i % 17 == 0 ||
        i % 19 == 0 || i % 23 == 0 || i % 29 == 0 || i % 31 == 0 ||
        i % 37 == 0 || i % 41 == 0 || i % 43 == 0 || i % 47 == 0 ||
        i % 53 == 0 || i % 59 == 0 || i % 61 == 0 || i % 67 == 0 ||
        i % 71 == 0 || i % 73 == 0) {
      continue;
    }
    int const current = prev * i;
    if (current % 9 == 0) {
      continue;
    }
    if (current > 75) {
      break;
    }
    ret += count75(current, counts, startIdx + 1);
  }
  return ret;
}

int calc(int n) {
  constexpr int primeCount = 25;
  constexpr int primes[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
                            43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
  if (n <= 1) {
    return 0;
  }
  std::vector<int> primeCounts(primeCount + 1, 0);
  for (int i = 2; i <= n; ++i) {
    int ii = i;
    for (int pIdx = 0; ii > 1 && pIdx < primeCount; ++pIdx) {
      int const prime = primes[pIdx];
      if (ii < prime) {
        break;
      }
      while (ii % prime == 0) {
        ii /= prime;
        primeCounts[pIdx]++;
      }
    }
  }
  std::sort(primeCounts.rbegin(), primeCounts.rend());
  return count75(1, primeCounts, 0);
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n;
  std::cin >> n;
  std::cout << calc(n) << std::endl;
  return 0;
}


Measured memory_bytes: 256
n=int(input())
p=[]
m=[]
bb=0
tt=False
for i in range(n):
    x,y=list(map(int,input().split()))
    p.append(x+y)
    m.append(x-y)
    bb+=1

minp=min(p)
maxp=max(p)
minm=min(m)
maxm=max(m)

ans=[maxp-minp,maxm-minm,minm,maxm,minp-maxp]
print(max(ans))

Measured memory_bytes: 24924
def main():
    a, b, m = map(int, input().split())
    a_lst = list(map(int, input().split()))
    b_lst = list(map(int, input().split()))
    xyc_lst = [list(map(int, input().split())) for _ in range(m)]

    min_a = min(a_lst)
    min_b = min(b_lst)
    ans = min_a + min_b

    for i in range(m):
        x = xyc_lst[i][0]
        y = xyc_lst[i][1]
        c = xyc_lst[i][2]

        cost = a_lst[x - 1] + b_lst[y - 1] - c

        if cost < ans:
            ans = cost

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 101020
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use itertools_num::ItertoolsNum;
#[allow(unused_imports)]
use proconio::{fastout, input, marker::Bytes, marker::Chars, marker::Isize1, marker::Usize1};
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::iter;
#[allow(unused_imports)]
use superslice::*;

fn run() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let a: i64 = sc.read();
    let b: i64 = sc.read();
    let c: i64 = sc.read();
    let d: i64 = sc.read();

    let mut ans = std::i64::MIN;
    for x in vec![a, b] {
        for y in vec![c, d] {
            ans = cmp::max(ans, x * y);
        }
    }
    println!("{}", ans);
}

fn main() {
    std::thread::Builder::new()
        .name("run".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(run)
        .unwrap()
        .join()
        .unwrap();
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn read_pairs<T: std::str::FromStr>(&mut self, n: usize) -> Vec<(T, T)> {
        (0..n).map(|_| (self.read(), self.read())).collect()
    }
    pub fn read_pairs_1_indexed(&mut self, n: usize) -> Vec<(usize, usize)> {
        (0..n)
            .map(|_| (self.read::<usize>() - 1, self.read::<usize>() - 1))
            .collect()
    }
    pub fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    pub fn read_char_grid(&mut self, n: usize) -> Vec<Vec<char>> {
        (0..n).map(|_| self.read_chars()).collect()
    }
    pub fn read_matrix<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n)
            .map(|_| (0..m).map(|_| self.read()).collect())
            .collect()
    }
}


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

int main()
{
    int n, h, w;
    cin >> n >> h >> w;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      int a, b;
      cin >> a >> b;
      if (a >= h && b >= w) ans++;
    }
    cout << ans << endl;
}


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

string base26 (long long n)
{
    string t = "zabcdefghijklmnopqrstuvwxy" ,res;
    while(n > 0)
    {
        long long x = n%26;
        res = t[x]+res;
        n = ceil((double)n/26)-1;
    }
    return res;
}

int main()
{
    long long n;
    cin >> n;
    cout << base26(n)<<endl;
    return 0;
}

Measured memory_bytes: 3620
a, b, c, d = map(int, input().split())

x1 = abs(a - b)
x2 = abs(b - c)
ac = abs(a - c)

if ac <= d:
    print('Yes')
elif (x1 <= d) and (x2 <= d):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MN = 1000100;
const ll M = 1e9+7;
ll mul(ll a, ll b) {
	return (a*b)%M;
}
ll bp(ll b, ll p) {
	ll ac = 1;
	while(p) {
		if(p&1) {ac = mul(ac,b);}
		b = mul(b,b);
		p >>= 1;
	}
	return ac;
}
ll inv(ll v) {return bp(v,M-2);}
ll fp[MN];
ll fac(ll n) {
	if(n <= 1) {return 1;}
	if(n >= 10000) {fac(n-10000);}
	if(fp[n] != -1) {return fp[n];}
	return fp[n] = mul(n,fac(n-1));
}
ll ch(ll n, ll k) {
	return mul(fac(n),mul(inv(fac(k)),inv(fac(n-k))));
}
int main() {
	ll n;
	cin >> n;
	memset(fp,-1,sizeof(fp));
	ll res = 0;
	ll rs = 0;
	for(int i=0;i<=n-2;i++) {
		if(i >= n-i-2) {
			ll ro = ch(i,n-i-2);
			ro = mul(ro,fac(i+1));
			ro = mul(ro,fac(n-2-i));
			ro -= rs;
			if(ro < 0) {ro += M;}
			rs += ro;
			if(rs >= M) {rs -= M;}
			res += mul(ro,i+1);
		}
	}
	res %= M;
	cout << res << '\n';
}


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

struct Point { double x, y; };

void koch(int n, Point a, Point b) {
    if (n == 0) return;

    Point s, t, u;
    double th = M_PI * 60.0 / 180.0;

    s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
    s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
    t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
    t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
    u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
    u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

    koch(n - 1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);

    koch(n - 1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);

    koch(n - 1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);

    koch(n - 1, t, b);
}

int main() {
    Point a, b;
    int n;

    scanf("%d", &n);

    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;

    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);

    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

const int INF = 1001001001;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

void solve() {
  int n;
  cin >> n;
  vi32 a(n);
  cin >> a;
  vi32 cnt(100001);
  rep(i, n) cnt[a[i]] += 1;
  i64 sum = 0;
  rep(i, n) sum += a[i];
  int q;
  cin >> q;
  rep(qi, q) {
    i64 b, c;
    cin >> b >> c;
    sum = sum - b * cnt[b] + c * cnt[b];
    cout << sum << '\n';
    cnt[c] += cnt[b];
    cnt[b] = 0;
  }
}


Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define Mod 1000000007
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
#define INF (ll)(1e17+5)
#define NN (ll)(1e6+5)
int mod(string s,int a) 
{ 
    int ans=0; 
    for (int i=0;i<s.length();i++) 
         ans=(ans*10+(int)s[i]-'0')%a; 
    return ans; 
}
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {    
       dd l,h,b,w;
       cin>>l;
       h=l/3;
       l-=h;
       b=l/2;
       w=l-b;
       cout<<fixed<<setprecision(12)<<h*b*w<<"\n";
   }
}

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

const int N = 1e5 + 10;
vector<int> edges[N];
bool visited[N];
int d[N];

void dfs(int i)
{
	visited[i] = 1;
	d[i] = -1;
	for(int v : edges[i])
	{
		if(!visited[v])
			dfs(v);
		d[i] = max(d[i],d[v]);
	}
	d[i]++;

}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		edges[a].push_back(b);
	}
	int answer = 0;
	for(int i = 1; i <= n; i++)
	{
		if(!visited[i])
		{
			dfs(i);
			answer = max(answer,d[i]);
		}
	}
	cout<<answer<<endl;
	return 0;
}

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


const int MAXN = 1005;

int main() {
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  set<ll>G;
  ll sum=0;
  rep(i,n)sum+=a[i];
  //cout<<sum;
  for(int i=1;i*i<=sum;i++){
    if (sum%i==0){
      G.insert(i);
      G.insert(sum/i);
    }
  }
ll ans=1;
  for(ll x:G){
  //  cout<<x<<'x'<<endl;
    vector<ll> r(n);
    rep(i,n)r[i]=a[i]%x;
    sort(r.begin(),r.end());
    ll cnt1=0;
    ll cnt2=0;

    rep(i,n)cnt1+=x-r[i];
    ll need=1e18;
    rep(i,n){
      cnt1-=x-r[i];
      cnt2+=r[i];

      need=min(need,max(cnt1,cnt2));
    //  cout<<cnt1<<'1'<<cnt2<<'2'<<endl;
        }
    if (need<=k) ans=max(ans,x);
  }
cout<<ans;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
P =[]
for i in range(K):
    d = int(input())
    e = input().split()
    P.append(e)

Q = []
for j in range(len(P)):
    for k in range(N):
        if str(k+1) in P[j]:
            if str(k+1) not in Q:
                Q.append(str(k+1)) 

print(N-len(Q))

Measured memory_bytes: 9456
MOD = 10**9 + 7

N = int(input())
As = list(map(int, input().split()))

ans = 1
numRGBs = [0] * 3
for A in As:
    num = 0
    for i in range(3):
        if numRGBs[i] == A:
            num += 1
            if num == 1:
                numRGBs[i] += 1
    ans *= num
    ans %= MOD

print(ans)


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

def ferris_wheel(age, fee):
    if 6 <= age <= 12:
        fee //= 2
    elif age <= 5: 
        fee = 0
    print(fee)


def main():
    a,b = [int(i) for i in input().split()] # 年齢 乗車量
    ferris_wheel(a,b)
    
# main関数呼び出し
if __name__ == "__main__":
    main() 

Measured memory_bytes: 2940
rooms = [[[0 for _ in range(10)] for _ in range(3)] for _ in range(4)]
n = int(input())
for _ in range(n):
    info = list(map(int,input().split()))
    rooms[info[0]-1][info[1]-1][info[2]-1] += info[3]

for b in range(4):
    for f in rooms[b] :
        print(" " + " ".join(list(map(str,f))))
    if b != 3:
        print("#"*20)

Measured memory_bytes: 7744
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)<(b))?(b):(a))

int main(void)
{
    int N;
    scanf("%d",&N);
    int *A = malloc(sizeof(int)*(N+1));
    int *B = malloc(sizeof(int)*N);
    for(int i=0;i<N+1;i++) scanf("%d",&A[i]);
    for(int i=0;i<N;i++) scanf("%d",&B[i]);
    
    long ans = 0;
    for(int i=0;i<N;i++)
    {
        if (A[i] < B[i])
        {
            ans += A[i];
            B[i] -= A[i];
            A[i] = 0;
        }
        else
        {
            ans += B[i];
            A[i] -= B[i];
            B[i] = 0;
        }
        if (A[i+1] < B[i])
        {
            ans += A[i+1];
            B[i] -= A[i+1];
            A[i+1] = 0;
        }
        else
        {
            ans += B[i];
            A[i+1] -= B[i];
            B[i] = 0;
        }
    }
    free(A);
    free(B);
    printf("%ld\n",ans);
}


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

int main(){
  int d,n;
  cin >> d >> n;
  vector<int> t(d);
  for(int i=0;i<d;i++)cin >> t[i];

  vector<int> a(n),b(n),c(n);
  for(int i=0;i<n;i++)cin >> a[i] >> b[i] >> c[i];

  vector< vector<int> > dp(d, vector<int>(n,-1) );
  for(int i=0;i<n;i++){
    if(a[i] <= t[0] && t[0] <= b[i])dp[0][i] = 0;
  }

  for(int i=1;i<d;i++){
    for(int j=0;j<n;j++){
      if(dp[i-1][j]<0)continue;
      for(int k=0;k<n;k++){
	if(a[k] <= t[i] && t[i] <= b[k]){
	  int dif = abs(c[j] - c[k]);
	  dp[i][k] = max(dp[i][k], dp[i-1][j] + dif);
	}
      }
    }
  }

  int ans = 0;
  for(int i=0;i<n;i++)ans = max(ans, dp[d-1][i]);
  cout << ans << endl;
}
  

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

int main() {
	string s;
	long long n, q;
	cin >> n >> q;
	cin >> s;
	long long a, b, num = 0;
	long long c[n];
	for(int i = 0;i < n; i++){
		c[i] = 0;
	}
	for(int i = 0; i < n - 1; i++){
		if(s[i] == 'A' && s[i + 1] == 'C'){
			num++;
			
		}
		c[i + 1] = num;
	}
	c[n-1] = num;
	
	for(int i = 0; i < q; i++){
		cin >> a >> b;
		cout << c[b -1] - c[a - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
using P = pair<int, int>;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<P> res;
    if (N % 2) // 奇数の時はすんなりと構成できる
    {
        for (int l = 1, r = N-1; l < r; ++l, --r)
        {
            res.emplace_back(l, r);   
        }
    }
    else // 偶数の時は途中で規則を切り替える必要がある
    {
        bool flag = false;
        for (int l = 1, r = N-1; l < r; ++l, --r)
        {
            if (!flag && r - l<= N / 2)
            {
                --r;
                flag = true;
            }
            res.emplace_back(l, r);
        }
    }
    for (int i = 0; i < M; ++i)
    {
        cout << res[i].first << " " << res[i].second << endl;
    }
    return 0;
}


Measured memory_bytes: 4316
//package AtCoderDp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        int h[]=new int[n+1];
        st=new StringTokenizer(br.readLine());
        long dp[]=new long[n+1];
        for(int i=1;i<=n;i++){
            h[i]=Integer.parseInt(st.nextToken());
        }
        dp[n-1]=Math.abs(h[n]-h[n-1]);
        for(int i=n-2;i>=1;i--){
            dp[i]=Long.MAX_VALUE;
            for(int j=i+1;j<=i+k&&j<=n;j++){
                dp[i]=Math.min(dp[i],dp[j]+Math.abs(h[j]-h[i]));
            }
        }
        System.out.println(dp[1]);
    }
}


Measured memory_bytes: 44628
import java.text.*;
import java.math.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		Card card = new Card();
		int kazu = scan.nextInt();
		String type ;
		int num;
		
		for(int i = 0; i < kazu; i++) {
			type = scan.next();
			num = scan.nextInt();
			card.setCard(type, num);
		}
		card.getNai();
	}
}

class Card {
	private boolean[][] tcard = new boolean[4][13];
	
	public void setCard (String c, int n) {
		int num = n - 1;
		int card = passType(c);
		tcard[card][num] = true;
	}
	public void getNai () {
		for(int i1 = 0;i1 < 4;i1++) {
			for(int i2 = 0;i2 < 13;i2++) {
				boolean t = tcard[i1][i2];
				if(t == false) {
					if(i1 == 0) {
						System.out.print('S');
					}else if(i1 == 1) {
						System.out.print('H');
					}else if(i1 == 2) {
						System.out.print('C');
					}else if(i1 == 3) {
						System.out.print('D');
					}
					int num = i2 + 1;
					System.out.println(" " +num); 
				}
			}
		}
	}
	private int passType (String type) {
		if(type.equals("S")) {
			return 0;
		}else if(type.equals("H")) {
			return 1;
		}else if(type.equals("C")) {
			return 2;
		}else { // if(type.equals("D")) {
			return 3;
		}
	}
}

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

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

int main() {
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    long long g = C * D / gcd(C, D);
    long long r1 = B / C - (A - 1) / C;
    long long r2 = B / D - (A - 1) / D;
    long long r3 = B / g - (A - 1) / g;
    cout << B - A + 1 - r1 - r2 + r3 << endl;
}

Measured memory_bytes: 256
N = int(input())
dp = list(range(N + 1))

for i in range(N + 1):
    pom6 = 1
    while pom6 <= i:
        dp[i] = min(dp[i], dp[i - pom6] + 1)
        pom6 *= 6

    pom9 = 1
    while pom9 <= i:
        dp[i] = min(dp[i], dp[i - pom9] + 1)
        pom9 *= 9

print(dp[N])

Measured memory_bytes: 42348
#include<iostream>
#include <string>
using namespace std;
int main(){
	string a;
	getline(cin,a);
	for(int i=0;i < a.size();i++){
		if('A'<=a[i] && a[i]<='Z'){
			a[i]+=32;
		}else if('a'<=a[i] && a[i]<='z'){
			a[i]-=32;
		}
		cout<<a[i];
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 3120
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<sstream>
#include<list>
#include<climits>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define nrep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;
#define M 1000000007

int main(){
	int n,m;cin>>n>>m;
	if(abs(n-m)>1){
		printf("0\n");
		return 0;
	}
	ll ret=n==m?2:1;
	rep(i,n)ret=ret*(n-i)%M;
	rep(i,m)ret=ret*(m-i)%M;
	cout<<ret<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) 
{
	int a,b;
	cin>>a>>b;
	cout<<(a-1)*(b-1);
	return 0;
}

Measured memory_bytes: 256