akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

typedef long long ll;

ll ab[100005];

int main() {
	int n; ll k; cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		ab[a] += b;
	}

	ll cnt = 0;
	for (int i = 1; i < 100005; i++) {
		cnt += ab[i];
		if (cnt >= k) {
			cout << i << endl;
			return 0;
		}
	}

	return 0;
}

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

typedef long long ll;

class dice
{
    public:
        int men[6];
        void N();
        void S();
        void W();
        void E();
        void circle();
};

void dice::N()
{
    int tmp;
    tmp = men[0];
    men[0] = men[1];
    men[1] = men[5];
    men[5] = men[4];
    men[4] = tmp;
}

void dice::S()
{
    int tmp;
    tmp = men[0];
    men[0] = men[4];
    men[4] = men[5];
    men[5] = men[1];
    men[1] = tmp;
}
void dice::W()
{
    int tmp;
    tmp = men[0];
    men[0] = men[2];
    men[2] = men[5];
    men[5] = men[3];
    men[3] = tmp;
}

void dice::E()
{
    int tmp;
    tmp = men[0];
    men[0] = men[3];
    men[3] = men[5];
    men[5] = men[2];
    men[2] = tmp;
}

void dice::circle()
{
    int tmp;
    tmp = men[1];
    men[1] = men[2];
    men[2] = men[4];
    men[4] = men[3];
    men[3] = tmp;
}

int main()
{
    int i,j,k;
    dice dice_first,dice_second;
    for(i = 0;i < 6;++i){
        cin >> dice_first.men[i];
    }
    for(i = 0;i < 6;++i){
        cin >> dice_second.men[i];
    }
    for(i = 0;i < 4;++i){
        for(j = 0;j < 4;++j){
            bool flag = true;
            for(k = 0;k < 6;++k){
                if(dice_first.men[k] != dice_second.men[k]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                cout << "Yes" << endl;
                return 0;
            }
            dice_first.circle();
        }
        dice_first.S();
    }
    dice_first.W();
    for(i = 0;i < 4;++i){
        bool flag = true;
        for(k = 0;k < 6;++k){
            if(dice_first.men[k] != dice_second.men[k]){
                flag = false;
                break;
            }
        }
        if(flag){
            cout << "Yes" << endl;
            return 0;
        }
        dice_first.circle();
    }
    dice_first.E();
    dice_first.E();
    for(i = 0;i < 4;++i){
        bool flag = true;
        for(k = 0;k < 6;++k){
            if(dice_first.men[k] != dice_second.men[k]){
                flag = false;
                break;
            }
        }
        if(flag){
            cout << "Yes" << endl;
            return 0;
        }
        dice_first.circle();
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3116
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = LI()
    t = sorted([a[i]-i-1 for i in range(n)])
    b = t[n//2]
    r = 0
    for i in range(n):
        r += abs(a[i]-(b+i+1))

    return r



print(main())


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

using ll = long long;
using ull = unsigned long long;
using namespace std;
constexpr int inf = 1<<30;
constexpr int mo = 1e9+7;
constexpr ll infl = 1ll<<60;

vector<pair<int,int>> Y[200105];
vector<pair<int,int>> XY[500005];
int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    
    int n;
    cin>>n;
    vector<tuple<int,int,char>> v;
    for(int i=0;i<n;++i){
        int x,y;
        char c;
        cin>>x>>y>>c;
        v.emplace_back(x,y,c);
    }
    auto rotate = [&](){
        for(auto & a : v){
            int x,y;char c;
            tie(x,y,c) = a;
            switch(c){
                case 'U':
                    c = 'R';
                    break;
                case 'R':
                    c = 'D';
                    break;
                case 'D':
                    c = 'L';
                    break;
                case 'L':
                    c = 'U';
                    break;
            }
            get<0>(a) = y;
            get<1>(a) = 200000 - x;
            get<2>(a) = c;
        }
    };
    auto st = [&]()->int{
        int ret = inf;
        for(int i=0;i<=200050;++i)Y[i].clear();
        for(auto &a : v){
            int x,y;char c;
            tie(x,y,c) = a;
            if(!(c == 'L' or c == 'R'))continue;
            Y[y].push_back({x,c});
        }
        
        for(int i=0;i<=200000;++i){
            sort(Y[i].begin(),Y[i].end());
            for(int j=0;j<(int)Y[i].size()-1;++j){
                if(!(Y[i][j].second == 'R' and Y[i][j+1].second == 'L'))continue;
                ret = min(ret,Y[i][j+1].first - Y[i][j].first);
            }
        }
        if(ret == inf)return ret;
        return ret*5;
    };
    auto cub = [&]()->int{
        int ret = inf;
        for(int i=0;i<=500000;++i)XY[i].clear();
        for(auto & a : v){
            int x,y;char c;
            tie(x,y,c) = a;
            if(!(c == 'R' or c == 'U'))continue;
            XY[x+y].push_back({x,c});
        }
        for(int i=0;i<=500000;++i){
            sort(XY[i].begin(),XY[i].end());
            for(int j=0;j<(int)XY[i].size()-1;++j){
                if(!(XY[i][j].second == 'R' and XY[i][j+1].second == 'U'))continue;
                ret = min(ret,XY[i][j+1].first - XY[i][j].first);
            }
        }
        if(ret == inf)return ret;
        return ret*10;
    };
    int ret = inf;
    for(int i=0;i<4;++i){
        int value1 = st();
        int value2 = cub();
        ret = min({ret,value1,value2});
        rotate();
    }
    if(ret == inf)cout << "SAFE" << endl;
    else cout << ret << endl;
    return 0;
    
}

Measured memory_bytes: 34856
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr> () -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let a = read::<usize>();
    let b = read::<usize>();
    println!("{:?}", std::cmp::min(a*n, b));
}


Measured memory_bytes: 4352
DMAX=17

def func(x,n)
    return if n==1
    gcds=[]
    (n/2).times do |i|
        gcds[i]=x[-1][2*i].gcd(x[-1][2*i+1])
    end
    x << gcds
    func(x,n/2)
end

def func2(x,i,level,temp)
    return if level==DMAX
    t=(i>>DMAX-level-1) ^ 1
    temp << x[DMAX-level-1][t]
    func2(x,i,level+1,temp)
end


def func3(a,n)
    x1=Array.new
    x1 << a
    func(x1,2**DMAX)
    max=0
    n.times do |i|
        temp=[]
        func2(x1,i,0,temp)
        g=temp.inject(&:gcd)
        max=g if max<g
    end
    return max
end

N=gets.to_i
A=gets.split.map(&:to_i)
A2=Array.new(2**DMAX,A[-1])
A3=Array.new(2**DMAX,A[-2])
A.each_with_index do |a,i|
    A2[i]=a
    A3[i]=a
end
puts [func3(A2,N),func3(A3,N)].max

Measured memory_bytes: 19028
import sys
input = sys.stdin.readline
read = sys.stdin.read

n, k = map(int, input().split())
m = map(int, read().split())
AB = list(zip(m, m))
k_bin = bin(k)[2:]
l = len(k_bin)
def count(d):
  s = 0
  for a, b in AB:
    if a & ~d:
      continue
    s += b
  return s

ans = count(k)
for i in range(l):
  if (k >> i) & 1:
    d = ((k >> i) << i) - 1
    temp = count(d)
    ans = max(ans, temp)
print(ans)

Measured memory_bytes: 30724
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
#![macro_use]

use std::cmp::*;
use std::collections::*;
use std::mem::*;
use std::num::*;
use std::ops::*;

const MOD: isize = 1000000007;

fn main() {
    let (N, K) = {
        let v: Vec<isize> = read_vec();
        (v[0], v[1])
    };
    let A: Vec<usize> = read_vec();

    let mut dp = vec![vec![-1isize; 2]; 55];
    dp[0][0] = 0;
    dp[49][0] = 0;

    for keta in (0..50).rev() {
        let mut cnt = A.iter().filter(|&x| x >> keta as i64 & 1 == 1).count() as isize;

        if (dp[keta + 1][1] != -1) {
            dp[keta][1] = max(
                dp[keta][1],
                dp[keta + 1][1] + max(cnt, N - cnt) * (1isize << keta),
            );
        }

        if (dp[keta + 1][0] != -1) {
            if (K >> keta & 1 == 1) {
                dp[keta][1] = max(dp[keta][1], dp[keta + 1][0] + cnt * (1isize << keta));
                dp[keta][0] = max(dp[keta][0], dp[keta + 1][0] + (N - cnt) * (1isize << keta));
            } else {
                dp[keta][0] = max(dp[keta][0], dp[keta + 1][0] + cnt * (1isize << keta));
            }
        }
    }
    println!("{}", max(dp[0][0], dp[0][1]));
}
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

#define int long long
const int MAXN=2e5;
int a,b,n;
string s;
signed main(){
    cin>>n>>a>>b;
    int sum=a+b;
    int r = n%sum;
    sum=n/sum;
    if(r>=a)r=a;
    int ans = sum*a+r;
    cout<<ans;
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

int main() {
    int a, b;
    string op;
    while(1) {
        cin >> a >> op >> b;
        if (op == "+") {
            cout << a + b << endl;
        }else if (op == "-") {
            cout << a - b << endl;
        }else if (op == "*") {
            cout << a * b << endl;
        }else if (op == "/") {
            cout << a / b << endl;
        }else {
            break;
        }
    }
    return 0;
}

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

int main(){
  string s, t, u;
  cin >> s >> t >> u;
  string ans = "";
  ans += toupper(s[0]);
  ans += toupper(t[0]);
  ans += toupper(u[0]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  int n,e=100000000;
  cin>>n;
  for(int i=1;i<n;i++){
    int a=i,b=n-i,c=0,d=0;
    while(a>0){
      c+=a%10;
      a/=10;
    }
    while(b>0){
      d+=b%10;
      b/=10;
    }
    e=min(c+d,e);
  }
  cout<<e;
}
    

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

int N;
vector<vector<int> > graph(N, vector<int>(0));
vector<vector<int> > children(N, vector<int>(0));
vector<long long> cnt(N, 0);
vector<bool> seen(N, false);

void child(int id, int parent)
{
    //cout << "child呼び出し: " << id << endl;
    if (!seen[id])
    {
        seen[id] = true;
        for (int i=0; i<graph[id].size(); i++)
        {
            if (graph[id][i]!=parent)
            {
                children[id].push_back(graph[id][i]);
                child(graph[id][i], id);
            }
        }
    }
}

void flow(int id)
{
    if (!seen[id])
    {
        seen[id] = true;
        for (int i=0; i<children[id].size(); i++)
        {
            int child = children[id][i];
            cnt[child] += cnt[id];
            flow(child);
        }
    }
}

int main()
{
    int Q;
    cin >> N >> Q;
    graph = vector<vector<int> > (N, vector<int>(0));
    children = vector<vector<int> > (N, vector<int>(0));
    cnt = vector<long long> (N, 0);
    seen = vector<bool> (N, false);
    for (int i=0; i<N-1; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }

    child(0, -1);
    /*
    for (int i=0; i<N; i++)
    {
        cout << i <<"の子供: ";
        for (int j=0; j<children[i].size(); j++)
        {
            cout << children[i][j] << " ";
        }
        cout << endl;
    }
    */
    seen = vector<bool> (N, false);

    for (int i=0; i<Q; i++)
    {
        seen = vector<bool> (N, false);
        int p, x;
        cin >> p >> x;
        cnt[p-1] += x;
    }
    flow(0);
    for (int i=0; i<N; i++) cout << cnt[i] << " ";
    cout << endl;
}

Measured memory_bytes: 48572
/**
 *    created by : PawPaw       
**/

#include<bits/stdc++.h>
using namespace std;

#define F(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define LL long long
#define N 100001
#define PB push_back
#define MP make_pair


int solve(){
  int n, k, pre[N];
  vector<int> ans;
  string s;
  cin >> n >> k;
  cin >> s;
  reverse(s.begin(), s.end());
  pre[0] = 0;
  F(i, 1, n){
    if(s[i] == '0'){
      pre[i] = i;
    } else {
      pre[i] = pre[i-1];
    }
  }
  int i = 0, curr;
  while(i < n){
    curr = pre[min(i+k, n)];
    if(curr == i){
      cout << "-1\n";
      return 0;
    }
    ans.push_back(curr-i);
    i = curr;
  }
  reverse(ans.begin(), ans.end());
  F(i, 0, (int)ans.size()-1){
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << '\n';
  return 0;
}

void fun(){
  int t = 1;
  // cin >> t;
  while(t--) solve();
} 

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

  fun();

  return 0;
}

Measured memory_bytes: 1480
#include <stdio.h>

/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(int arr[],int n) {
	int target;
	int i;
	int temp;
	for (i = n - 2; i >= 0; i--) {
		if (arr[i] < arr[i + 1]) break;
	}
	if (i < 0) return 0;
	target = i;

	for (i = 0; target + i + 1 < n - i - 1; i++) {
		temp = arr[target + 1 + i];
		arr[target + 1 + i] = arr[n - 1 - i];
		arr[n - i - 1] = temp;
	}

	for (i = target + 1; i < n; i++) {
		if (arr[i] > arr[target]) break;
	}
	temp = arr[i];
	arr[i] = arr[target];
	arr[target] = temp;
	return 1;
}

/*
 1
4025
 3
*/
int connect[12][4] = {
	/* {pos, h/w, pos, h/w} */
	{0, 1, 1, 1},
	{0, 0, 2, 0},
	{0, 1, 3, 1},
	{0, 0, 4, 0},

	{1, 0, 2, 1},
	{2, 1, 3, 0},
	{3, 0, 4, 1},
	{4, 1, 1, 0},

	{5, 1, 1, 1},
	{5, 0, 4, 0},
	{5, 1, 3, 1},
	{5, 0, 4, 0}
};

int main(void) {
	int hw[6][2];
	int i;
	int permutation[6] = {0, 1, 2, 3, 4, 5};
	int rotate;
	for (i = 0; i < 6; i++) {
		if (scanf("%d%d", &hw[i][0], &hw[i][1]) != 2) return 1;
	}
	do {
		for (rotate = 0; rotate < (1 << 6); rotate++) {
			int ng = 0;
			for (i = 0; i < 12; i++) {
				int len1 = hw[permutation[connect[i][0]]][connect[i][1] ^ ((rotate >> connect[i][0]) & 1)];
				int len2 = hw[permutation[connect[i][2]]][connect[i][3] ^ ((rotate >> connect[i][2]) & 1)];
				if (len1 != len2) {
					ng = 1;
					break;
				}
			}
			if (!ng) {
				puts("yes");
				return 0;
			}
		}
	} while (next_permutation(permutation, 6));
	puts("no");
	return 0;
}

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

int main(){
  int i,j;ll cnt;
  int n;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)cin>>a[i];
  ll sum=0;
  for(i=0;i<n;i++)sum+=a[i];
  cnt=0;
  ll mi=INT_MAX;
  for(i=0;i<n;i++){
    cnt+=a[i];
    mi=min(max(sum-2*cnt,2*cnt-sum),mi);
  }
  cout<<mi;
}

Measured memory_bytes: 1792
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	S := reverse(sc.nextStr())
	words := []string{reverse("dream"), reverse("dreamer"), reverse("erase"), reverse("eraser")}
	ans := true
	for 0 < len(S) {
		ok := false
		for _, w := range words {
			if strings.HasPrefix(S, w) {
				ok = true
				S = S[len(w):]
				break
			}
		}
		if !ok {
			ans = false
			break
		}
	}

	if ans {
		fmt.Fprintln(wtr, "YES")
	} else {
		fmt.Fprintln(wtr, "NO")
	}
	wtr.Flush()
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  string s;
  cin >> s;
  ll n=s.size();
  ll ans=0;
  for(ll i=0;i<n;i++) {
    ans+=s[i]=='2';
  }
  cout << ans << endl;
}

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

#define INF 1000000010
#define INFLL ((1LL<<62)-5)
#define FO(i,a,b) for (int (i) = (a); (i) < (b); ++(i))
#define sz(v) int(v.size())

using namespace std;
//PAIRS:
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pii;
typedef long long ll;

/*~~~~TEMPLATE END~~~~*/
#define MAX_N 5005

int N, K;
vector <int> allC[MAX_N];
int par[MAX_N];
int dp[MAX_N][MAX_N];
int newDP[MAX_N];
int sz[MAX_N];

vector <int> allE[MAX_N];

int ans(INF);
void makeTree (int c) {
    FO (i,0,allE[c].size()) {
        if (allE[c][i] != par[c]) {
            int nx = allE[c][i];
            par[nx] = c;
            allC[c].push_back (nx);
            makeTree(nx);
            sz[c] += sz[nx];
        }
    }
    sz[c]++;
}

void doDP(int c) {
    FO (i,0,allC[c].size()) doDP(allC[c][i]);
    FO (i,0,allC[c].size()) {
        int cC = allC[c][i];
        for (int p = K-1; p >= 0; p--) {
            dp[cC][p+1] = dp[cC][p];
        }
        dp[cC][0]++;
        FO (p,0,K+1) {
            newDP[p] = INF;
        }
        FO (p,0,K+1) {
            int oth = K-p;
            newDP[p] = min(dp[c][p]+dp[cC][min(p,oth)],dp[c][min(p,oth)]+dp[cC][p]);
        }
        FO (p,0,K+1) dp[c][p] = newDP[p];
        FO (p,1,K+1) dp[c][p] = min(dp[c][p],dp[c][p-1]);
    }
    ans = min (ans, dp[c][K]+N-sz[c]);
    /*FO (p,0,K+1) {
        printf ("dp[%d][%d]: %d\n", c, p, dp[c][p]);
    }*/
}

int main() {
    scanf ("%d %d", &N, &K);
    FO (i,0,N-1) {
        int _a, _b;
        scanf ("%d %d", &_a, &_b);
        allE[_a].push_back (_b);
        allE[_b].push_back (_a);
    }
    makeTree(1);
    doDP(1);
    printf ("%d\n", ans);
    return 0;
}


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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct UnionFind {
    // 親ノードの番号を持つメンバ変数
    // ただし自分が親の時は-x(xは自身を含めた子ノードの数)
    vector<int> par;
    
    //　コンストラクタでの初期化1(初期値-1を持つn次元配列)
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    // 与えられたノードの親ノードの番号を返すメンバ関数
    int root(int x) {
        // もしも親ノードが0以下なら、それは初期値なので自身が親
        if (par[x] < 0) return x;
        // 親ノードを再帰的に一番上までたどって返す
        // 単にroot(par[x])ではなく代入してるのは、根に直接張り直すため
        else return par[x] = root(par[x]);
    }
    
    // もし根が同じかどうかの判定
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    // ２つの根をマージする処理
    bool unite(int x, int y) {
        // 根をたどって、同じなら何もしない
        x = root(x); y = root(y);
        if (x == y) return false;
 
        // xもyも今は親ノードなので、子の数を比べる
        if (par[x] > par[y]) swap(x, y); // merge technique
 
        // 小さい方を親ノードにする
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    //　根の直下に葉を移動させる
    bool optimize(int x) {
        if( par[x] < 0 ) return false;
        else
        {
            par[x] = root(x);
            return true;
        }
    }
    
    // 親ノードに入っている番号*-1 = この木のノード数を返す。
    int size(int x) {
        return -par[root(x)];
    }
};


int main()
{
    int N,M;
    cin >> N >> M;

    UnionFind uf(N);

    vector<int> p(N);
    rep(i,N)
    {
        cin >> p[i];
        p[i]--;
    }

    rep(i,M)
    {
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        uf.unite(x,y);
    }

    ll ans = 0;
    rep(i,N)
    {
        if( !uf.same(i, p[i]) )ans++;
    }

    cout << N-ans << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>

int main() {
	int a, b, c, k;
	scanf("%d %d %d %d", &a, &b, &c, &k);
	if (k <= a) printf("%d", k);
	else if (k <= a + b) printf("%d", a);
	else printf("%d", 2 * a + b - k);


	return 0;
}

Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

int main() {
  int k, x;
  cin >> k >> x;

  if (k * 500 >= x) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f 
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100005
#define P pair<int,int>
using namespace std;
int a[200005];
int b[200005];
map<int, ll>mp;
double i, j, k, l;
int i1, k1, j2;

int main()
{
	int a, b;
	cin >> b >> a;
	int flag = 1;
	if (b == 1 && a == 0)
	{
		cout << "0";
		return 0;
	}
	int q[100];
	MEM(q, -1);
	while (a--)
	{
		int n, m;
		cin >> n >> m;
		if (q[n] == -1 || q[n] == m)
		{
			q[n] = m;
		}
		else
			flag = 0;
		if (n == 1 && m == 0)
			flag = 0;
	}
	if (b == 1 && q[1] == 0)
	{
		cout << "0";
		return 0;
	}
	if (flag)
	{
		for (int i = 1; i <= b; i++)
		{
			if (i == 1 && q[1] == -1)
				q[1] = 1;
			if (q[i] == -1)
				q[i] = 0;

			cout << q[i];
		}

	}
	else
		cout << "-1";
}







Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author bcools
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long n = in.nextInt();
            long a = in.nextInt();
            long b = in.nextInt();
            long res = 0;
            if (n < 1 || a > b) {
                res = 0;
            } else if (n == 1 && a == b) {
                res = 1;
            } else if (n == 1) {
                res = 0;
            } else {
                long min = a + b + (n - 2) * a;
                long max = a + b + (n - 2) * b;
                res = max - min + 1;
            }
            out.println(res);
        }

    }
}



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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define revrepeat(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define foreach(e, v) for (auto &e : v)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
constexpr int MOD = 1e9 + 7;
constexpr int INF = __INT_MAX__;               // 2^31 - 1
constexpr long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
constexpr int MAX_N = 1e5 + 5;
constexpr double PI = acos(-1);

struct mint {
    // Preparation: MOD is already defined.
    ll value;

    mint(ll value = 0) : value((value % MOD + MOD) % MOD) {}

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint pow(mint m) const {
        return pow(m.value);
    }

    mint inv() const {
        ll a = value, b = MOD, u = 1, v = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        return u;
    }

    mint &operator+=(const mint a) {
        if ((value += a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((value += MOD - a.value) >= MOD) value -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (value *= a.value) %= MOD;
        return *this;
    }
    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

int main() {
    int n, l;
    cin >> n >> l;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    sort(all(s));
    string ans = "";
    rep(i, n) {
        ans += s[i];
    }
    out(ans);
}


Measured memory_bytes: 256
import math

n=int(input())
plist = list(map(int, input().split()))
qlist = list(map(int, input().split()))

klist=[]
klist2=[]
for i in range(n):
    klist.append(i+1)
    klist2.append(i+1)

answer1=[]
answer2=[]


for j in range(n):
    numb=klist.index(plist[j])
    answer1.append(numb)
    klist=klist[:numb]+klist[numb+1:]

for j in range(n):
    numb=klist2.index(qlist[j])
    answer2.append(numb)
    klist2=klist2[:numb]+klist2[numb+1:]

#print(answer1)
#print(answer2)

answer3=0
answer4=0

for i in range(n):
    answer3+=math.factorial(n-i-1)*answer1[i]
    answer4+=math.factorial(n-i-1)*answer2[i]

print(abs(answer3-answer4))    

Measured memory_bytes: 38256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
#define int long long
#define veb vector<bool>
#define vveb vector<veb>
#define vel vector<long long>
#define vvel vector<vel>
#define vvvel vector<vvel>
void mmin(int &a, int b) { a = min(a, b); }
void mmax(int &a, int b) { a = max(a, b); }
void sor(vel &v) { sort(v.begin(), v.end()); }
void rev(vel &v) { reverse(v.begin(), v.end()); }
int zero(void) { return 0; }
signed main() {
	int k;
	cin >> k;
	cout << (k / 2)*((k + 1) / 2) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f3f;
const int maxn = 1e5+500;
ll T,n,m;
int num[maxn];
int a[maxn];
int main() {
   	cin>>n;
   	cout<<(n)*(n-1)/2<<endl;
}



Measured memory_bytes: 256
W,H,N=map(int,input().split())
A=0
B=W
C=0
D=H
for _ in range(N):
  x,y,a=map(int,input().split())
  if a==1:
    A=max(A,x)
  elif a==2:
    B=min(B,x)
  elif a==3:
    C=max(C,y)
  else:
    D=min(D,y)
print(max(B-A,0)*max(0,D-C))

Measured memory_bytes: 3064
//
//  main.cpp
//  zero
//
//  Created by 叶金炜 on 2019/4/2.
//  Copyright © 2019 okstal. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string.h>
#define pi acos(-1)
using namespace std;
int main() {
    int n,a[5][15],x;
    char c;
    cin>>n;
    memset(a, 0, sizeof(a));
    for(int i=1;i<=n;i++)
    {
        cin>>c>>x;
        if(c=='S')a[1][x]++;
        else if(c=='H')a[2][x]++;
        else if(c=='C')a[3][x]++;
        else if(c=='D')a[4][x]++;
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=13;j++)
            if(a[i][j]==0)
            {
                if(i==1)cout<<"S"<<" "<<j<<endl;
                else if(i==2)cout<<"H"<<" "<<j<<endl;
                else if(i==3)cout<<"C"<<" "<<j<<endl;
                else if(i==4)cout<<"D"<<" "<<j<<endl;
            }
    }
    return 0;
}



Measured memory_bytes: 3068
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int[] h = new int[300], w = new int[300];
		int cnt = 0;
		
		while(true){
			h[cnt] = sc.nextInt();
			w[cnt] = sc.nextInt();
			
			if(w[cnt] == 0 && h[cnt] == 0)
				break;
			
			cnt ++;
		}
		
		for(int i = 0; i < cnt; i++){
			for(int j = 0; j < h[i]; j++){
				for(int k = 0; k < w[i]; k++){
					if(j == 0 || j == h[i] - 1 || k == 0 || k == w[i] - 1)
						System.out.print("#");
					else
						System.out.print(".");
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}

Measured memory_bytes: 32264
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

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

    int ans = 0;
    for (int i = 0; i < max(b,d); ++i) {
        if(a <= i && b > i && c <= i && d > i)ans++;
    }
    print(ans);
}

Measured memory_bytes: 256
N=int(input())

a=N//1000
b=(N%1000)//100
c=(N%100)//10
d=N%10

ope=[-1,1]

for i in ope:
    for j in ope:
        for k in ope:
            if a+i*b+j*c+k*d==7:
                ans=[i,j,k]

l=[0]*3

for i in range(3):
    if ans[i]>0:
        l[i]="+"
    else:
        l[i]="-"

   

#all_ans=[str(a),l[0],str(b),l[1],str(c),l[2],str(d)]
all_ans=str(a)+l[0]+str(b)+l[1]+str(c)+l[2]+str(d)+"=7"
print(all_ans)

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

int main(){
  int N,m;
  cin >> N;
  
  vector<vector<int>> A(N,vector<int>(3));
  rep(i,N){
    rep(j,3)
      cin >> A.at(i).at(j);
  }
  
  vector<vector<int>> dp(N+1,vector<int>(3,0));
  
  rep(i,3)
  dp.at(0).at(i)=0;
  
  
  for(int i=1;i<=N;i++){
    rep(j,3){
      rep(k,2){
        if(j+k+1>2)
          dp.at(i).at(j)=max(dp.at(i-1).at(j+k-2)+A.at(i-1).at(j),dp.at(i).at(j));
        else
          dp.at(i).at(j)=max(dp.at(i-1).at(j+k+1)+A.at(i-1).at(j),dp.at(i).at(j));
      }
      
      
    }
  }
  
  
 /* rep(i,N+1){
    rep(j,3){
      cout << dp.at(i).at(j) << ' ';
    }
    cout << endl;
  }*/
  
  m=max(dp.at(N).at(0),dp.at(N).at(1));
  m=max(dp.at(N).at(2),m);
  cout << m << endl;
  
 
}






Measured memory_bytes: 11136
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

string name[1000];
int num[1000];
int year[1000];
int n,q;

int main() {
  while(cin >> n >> q, n||q) {
    REP(i,n) {
      cin >> name[i] >> num[i] >> year[i];
    }
    REP(i,q) {
      int y;cin >> y;
      bool f = 0;
      REP(j,n) {
        if (year[j]-num[j]+1 <= y && y<=year[j]) {
          cout << name[j] << " " << y-year[j]+num[j] << endl;
          f = 1;
          break;
        }
      }
      if (!f) cout << "Unknown" << endl;
    }  
  }
}

Measured memory_bytes: 980
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;

int n, i, a;
LL b, sum, cou, res;

int main() {
scanf("%d", &n);
cou = 0;
sum = 0;
for (i=0;i<n;i++) {
	scanf("%d %lld", &a, &b);
	sum += b * a;
	cou += b;
}
res = cou - 1 + (sum - 1) / 9;
printf("%lld\n", res);
return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int cnt = 0;
		for (int i = 1 ; i <= n ; i++) {
			int sum = i / 10000 + (i - i / 10000 * 10000) / 1000 + (i - i / 1000 * 1000) / 100 + (i - i / 100 * 100) / 10 + i % 10;
			if (a <= sum && b >= sum) cnt += i;
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 21840
#include<bits/stdc++.h>
using namespace std;
struct edge { int to,cap,rev; };
#define MAX 52
#define INF (1e7)
int n;
vector<int> G[MAX][MAX];
bool used[MAX];
vector<int> g[MAX];
vector<int> min(vector<int> &a,vector<int> &b){
  for(int i=MAX-1;i>=0;i--){
    if( a[i]==b[i] )continue;
    if(a[i]>b[i])return b;
    if(a[i]<b[i])return a;
  }
  return a;
}
 
void add(vector<int> &a,vector<int> &b){
  for(int i=0;i<MAX;i++)
    a[i]+=b[i];
}
 
void sub(vector<int> &a,vector<int> b){
  for(int i=0;i<MAX;i++)
    a[i]-=b[i];
}
 
bool check(vector<int> &a){
  for(int i=0;i<MAX;i++)
    if(a[i]>0)return true;
  return false;
}
 
vector<int> dfs(int v,int t,vector<int> f){
  if(v==t)return f;
  used[v]=true;
  for(int to=0;to<g[v].size();to++){
    int i=g[v][to];
    vector<int> &e=G[v][i];
    if(!used[i] && check(e) ){
      vector<int> d=dfs( i,t,min(f,e));
      if( d.size()==MAX && check(d) ){
        sub(G[v][i],d);
        add(G[i][v],d);
        return d;
      }
    }
  }
  return vector<int>();
}
 
vector<int> max_flow(int s,int t){
  vector<int> flow(MAX,0);
  while(1){
    memset(used,0,sizeof(used));
    vector<int> tmp(MAX,INF);
    vector<int> f=dfs(s,t,tmp);
    if(f.size()==0)return flow;
    add(flow,f);
  }
  return flow;
}
 
int m;
int t[MAX][MAX][MAX];
int u[MAX][MAX];
 
int s2i(string s){
  stringstream ss;
  int res;
  ss<<s;
  ss>>res;
  return res;
}
 
void func(int a,int b,string &tmp){
  int len=tmp.size();
  int flg=0;
  for(int i=0;i<len;i++){
    if('0'<=tmp[i]&&tmp[i]<='9')continue;
    flg=1;
  }
  if(flg==0){
    t[a][b][0]=t[b][a][0]=s2i(tmp);
    return;
  }
   
  int v,w;
  if(tmp[0]=='x')v=1;
  else{
    for(int i=0;i<len;i++){
      if(tmp[i]=='x'){
        v=s2i(tmp.substr(0,i));
        break;
      }
    }
  }
   
  if(tmp[len-1]=='x')w=1;
  else{
    for(int i=0;i<len;i++){
      if(tmp[i]=='^'){
        w=s2i(tmp.substr(i+1));
        break;
      }
    }
  }
  t[a][b][w]=t[b][a][w]=v;
}
 
int main(){
  while(1){
    cin>>n>>m;
    if(n==0&&m==0)break;
    memset(t,0,sizeof(t));
    memset(u,0,sizeof(u));
    for(int i=0;i<MAX;i++)g[i].clear();
    
    for(int i=0;i<m;i++){
      int a,b;
      string s,tmp;
      cin>>a>>b>>s;
      g[a].push_back(b);
      g[b].push_back(a);
      for(int j=0;j<(int)s.size();j++)
        if(s[j]=='+')s[j]=' ';
      stringstream ss(s);
      while(ss>>tmp){
        func(a,b,tmp);
      }
    }
 
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        G[i][j].clear();
        G[i][j].resize(MAX);
        for(int k=0;k<MAX;k++){
          G[i][j][k]=t[i][j][k];
        }
      }
    }
 
    vector<int> ans=max_flow(1,n);
    bool cnt=0;
    for(int i=MAX-1;i>=0;i--){
      if(ans[i]==0)continue;
      if(cnt>0)cout<<'+';
      cnt++;
      if(i==0||ans[i]>1)cout<<ans[i];
      if(i)cout<<'x';
      if(i>1)cout<<"^"<<i;
    }
    if(cnt==0)cout<<0;
    cout<<endl;
  }
  return 0;
}

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

bool Check(const std::vector<int>& A, int m, int i, int v)
{
    if(v == m) return true;
    if(v >  m) return false;
    for(i; i < A.size(); ++i){
        if(Check(A, m, i+1, v + A[i])){
            return true;
        }
    }
    return false;
}

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> A(n);
    for(int i = 0; i < n; ++i){
        std::cin >> A[i];
    }
    
    int q;
    std::cin >> q;
    for(int i = 0; i < q; ++i){
        int m;
        std::cin >> m;
        std::cout << (Check(A, m, 0, 0) ? "yes" : "no") << std::endl;
    }
    
    return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    int N;
    cin >> N;
    vector<int> d(N);
    REP(i, N) cin >> d[i];
    sort(All(d));
    d.erase(unique(All(d)), d.end());
    cout << d.size() << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  long A;
  int B1, B2;
  scanf("%lld %d.%d", &A, &B1, &B2);
  int B = 100 * B1 + B2;
  ll ans = A * B;
  ans /= 100;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int N;cin >> N;
    vector<int> T(N),A(N);
    rep(i,N)cin >> T[i];
    rep(i,N)cin >> A[i];
    using pii = pair<int,int>;//区間なら１、値なら０
    vector<pii> t(N),a(N);
    t[0]=make_pair(0,T[0]);
    for(int i=1;i<N;i++){
        int b = T[i-1]==T[i]?1:0;
        t[i]=make_pair(b,T[i]);
    }
    a[N-1]=make_pair(0,A[N-1]);
    for(int i=N-2;i>=0;i--){
        int b = A[i+1]==A[i]?1:0;
        a[i]=make_pair(b,A[i]);
    }
    ll res = 1;
    rep(i,N){
        int tf=t[i].first,af=a[i].first,ts=t[i].second,as=a[i].second;
        if(tf==0&&af==0){
            if(ts!=as)res*=0;
        }else if((tf==1&&af==0)){
            if(ts<as)res*=0;
        }else if(tf==0&&af==1){
            if(ts>as)res*=0;
        }else{
            res=res*min(ts,as)%(1000000007);
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
const long long mod_const = 1000000007;
using MIte = multimap<vector<long>, int>::iterator;

int main() {
	int M, D;
	cin >> M >> D;

	vector<int> vSeki(D+1, 0);
	for (int i = 1; i != D + 1; ++i) {
		int d10 = i / 10;
		int d1 = i - d10 * 10;
		if (d10 >= 2 && d1 >= 2){
			vSeki[i] = d10 * d1;
		}
	}

	int cnt = 0;
	for (int i = 1; i != M+1; ++i) {
		for (int j = 1; j != D+1; ++j) {
			if (i == vSeki[j]) {
				cnt++;
			}
		}
	}

	cout << cnt << endl;
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  if (s == "SUN") cout << 7 << endl;
  else if (s == "MON") cout << 6 << endl;
  else if (s == "TUE") cout << 5 << endl;
  else if (s == "WED") cout << 4 << endl;
  else if (s == "THU") cout << 3 << endl;
  else if (s == "FRI") cout << 2 << endl;
  else if (s == "SAT") cout << 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main() {
	int a, b, c;
	std::cin >> a >> b >> c;
	if (a < b) {
		if (b < c) {
			std::cout << "Yes" << std::endl;
		}
		else {
			std::cout << "No" << std::endl;
		}
	}
	else {
		std::cout << "No" << std::endl;
	}
	return 0;
}


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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod =1000000007;




int main() {
	int n, m;
	cin >> n >> m;

	VLL a(n);
	REP(i, n)cin >> a[i];

	VVI v(m, VI(2));
	REP(i, m) {
		cin >> v[i][1] >> v[i][0];
	}

	sort(ALL(a));
//	reverse(ALL(a));

	sort(ALL(v));
	reverse(ALL(v));

	int b = 0;
	int c = 0;

	while (b <n&&c<m) {
		if (a[b] < v[c][0]) {
			a[b] = v[c][0];
			if (v[c][1] == 1) {
				c++;
			}
			else {
				v[c][1]--;
			}
		}
		b++;

	}

	ll ans = 0;
	REP(i, n)ans += a[i];

	cout << ans << endl;

}



Measured memory_bytes: 6528
#include<iostream>
    #include<cmath>
    #include<iomanip>
    using namespace std;
    int main(){
      double A,B,H,M;
      cin>>A>>B>>H>>M;
      double angle_a,angle_b;
      angle_a=2*M_PI*H/12+M_PI/6*M/60;
      angle_b=2*M_PI*M/60;
      double angle=abs(angle_a-angle_b);
      double a_x,a_y,b_x,b_y;
      a_x=0;
      a_y=A;
      b_y=cos(angle)*B;
      b_x=sin(angle)*B;
      double dist=sqrt(A*A+B*B-2*A*B*cos(angle));
      cout<<fixed<<setprecision(16)<<dist<<endl;
      return 0;
    }

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

using namespace std;

int main() {
	int N;
	vector<int> x(5);
	for (int i = 0; i < 5; i++) {
		cin >> x.at(i);
	}

	for (int i = 0; i < 5; i++) {
		if (x.at(i) == 0) {
			cout << i+1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        private static int[][] Solve(int H, int W, int[] A)
        {
            int[][] C = new int[H][];
            for (int i = 0; i < H; ++i) { C[i] = new int[W]; }
            int c = 0;
            for (int i = 0; i < H * W; ++i)
            {
                while (A[c] == 0) { ++c; }
                int h = i / W;
                int w = (h % 2 == 0) ? i % W : W - i % W - 1;
                C[h][w] = c + 1;
                --A[c];
            }
            return C;
        }
        static void Main(string[] args)
        {
            int[] values = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = int.Parse(Console.ReadLine());
            int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            foreach (int[] c in Solve(values[0], values[1], A))
            {
                Console.WriteLine(string.Join(" ", c));
            }
        }
    }
}


Measured memory_bytes: 11360
class DisjointSet:
    def __init__(self,n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

    def same(self,x,y): 
        return self.findSet(x) == self.findSet(y)

    def unite(self,x,y): 
        return self.link(self.findSet(x), self.findSet(y))

    def link(self,x,y):
        if self.rank[x] > self.rank[y]: 
            self.parent[y] = x
            self.siz[x] += self.siz[y]
        else:
            self.parent[x] = y
            self.siz[y] += self.siz[x]
            if self.rank[x] == self.rank[y]: self.rank[y] += 1

    def findSet(self,x):
        if x != self.parent[x]: 
            self.parent[x] = self.findSet(self.parent[x])
        return self.parent[x]

    def size(self,x):
        return self.siz[self.findSet(x)]

n,m = map(int,input().split())
brg = [[int(i)-1 for i in input().split()] for _ in range(m)]
cnt = n*(n-1)//2
ans = [0]*m
ds = DisjointSet(n)
for i in range(m)[::-1]:
    ans[i] = cnt
    a,b = brg[i]
    if not ds.same(a,b):
        cnt -= ds.size(a)*ds.size(b)
        ds.unite(a,b)
print("\n".join(map(str,ans)))

Measured memory_bytes: 36744
#include <stdio.h>

int A[20];
int n;

int solve(int p, int t);
int sort(void *a, void *b);

int main(void) {
	int i, q, M;
	
	scanf("%d", &n);
	for (i = 0; i < n; ++i) {
		scanf("%d", &A[i]);
	}
	
	qsort(A, n, sizeof(A[0]), sort);
	
	scanf("%d", &q);
	for (i = 0; i < q; ++i) {
		scanf("%d", &M);
		if (solve(-1, M)) {
			printf("yes\n");
		} else {
			printf("no\n");
		}
	}
	
	return 0;
}

int solve(int p, int t) {
	if (t < 0) return 0;
	if (t == 0) return 1;
	if (p == n) return t == 0;
	return solve(p + 1, t - A[p + 1]) || solve(p + 1, t);
}

int sort(void *a, void *b) {
	return *(int*)b - *(int*)a;
}

Measured memory_bytes: 584