akhauriyash/Code-Regression huggingface dataset:
def main():
    N, M, X = [int(x) for x in input().split()]
    CA = [[int(x) for x in input().split()] for _ in range(N)]
    C = [CA[i][0] for i in range(N)]
    A = [CA[i][1:] for i in range(N)]

    def calc(bit):
        i = 0
        rikai = [0] * M
        cost = 0
        while bit > 0:
            if bit & 1:
                cost += C[i]
                for j in range(M):
                    rikai[j] += A[i][j]
            bit = bit >> 1
            i += 1
        if all(r >= X for r in rikai):
            return cost
        else:
            return None

    bit = 1
    ans = float("inf")
    while bit <= (2**N-1):
        cost = calc(bit)
        if cost is not None:
            ans = min(ans, cost)
        bit += 1
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()


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

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))

double dot(P a, P b) {
    return (a.X * b.X + a.Y * b.Y);
}
double cross(P a, P b) {
    return (a.X * b.Y - a.Y * b.X);
}

int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if( cross(b,c) > EPS ) return +1;
    if( cross(b,c) < -EPS ) return -1;
    if( dot(b,c) < 0 ) return +2;
    if( norm(b) < norm(c) ) return -2;
    return 0;
}

int main() {
    P a,b,c,d;
    while(cin >> a.X >> a.Y >> b.X >> b.Y >> c.X >> c.Y >> d.X >> d.Y) {
        int x = ccw(a,b,d);
        int y = ccw(b,c,d);
        int z = ccw(c,a,d);
        // printf("%d %d %d\n", x, y, z);
        if(x == 1 && y == 1 && z == 1) cout << "YES" << endl;
        else if(x == -1 && y == -1 && z == -1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 1228
#include <stdio.h>

int main(void)
{
	int a, b, c;
	
	scanf("%d %d", &a, &b);
	
	c = a + b;
	
	if(c < 24) {
		printf("%d", c);
	}
	else {
		printf("%d", c - 24);
	}
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
 
int main(void)
{
	int i,j,k,l,o,n=0;

	while(scanf("%d",&i) != EOF){
		for(j=0;j<=9;j++){
			for(k=0;k<=9;k++){
				for(l=0;l<=9;l++){
					for(o=0;o<=9;o++){
						if(i==j+k+l+o){
							n++;
						}
					}
				}
			}
		}
	printf("%d\n",n);
	n = 0;
	}
   return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
	using namespace std;
	#define IOS ios::sync_with_stdio(false), cin.tie(0)
	#define REP(i, n) for (int i = 0; i < n; i++)
	#define FOR(i, a, b) for (int i = a; i < b; i++)
	#define ALL(x) (x).begin(), (x).end()
	#define dump(x) cout << (x) << endl
	#define LMAX 9223372036854775807LL
	#define LMIN -9223372036854775807LL

	using ll = long long;
	template<typename T>
	using vec = vector<T>;
	using P = pair<ll, ll>;

	template <typename A, size_t N, typename T>
	void Fill(A (&array)[N], const T &val){
		fill((T *)array, (T *)(array + N), val);
	}
	
	const ll INF = 1e16;
	const ll MOD = 1e9 + 7;

	//int dx[4] = {1,0,-1,0};
	//int dy[4] = {0,1,0,-1};
	//ll pas[51][52];
	
	signed main(){
		IOS;
		int n, m;
		cin >> n >> m;
		vec<ll> sum(n + 1,1);
		vec<bool> red(n + 1,false);
		red[1] = true;
		REP(i, m){
			int x, y;
			cin >> x >> y;
			if(red[x])red[y] = true;
			sum[y]++;
			sum[x]--;
			if(sum[x] == 0)red[x] = false;
		}
		ll ans = 0;
		for(int i = 1;i <= n;i++){
			if(red[i])ans++;
		}
		dump(ans);
	}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

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

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 答え
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<iostream>
#include <algorithm>
#include <functional>
#include <array>
using namespace std;
void margesort(int a[], int a_len, int left, int right);
void margesortD(int a[], int b[], int a_len, int left, int right);
int temp[100000];
int tempb[100000];
int b[100000];
int c[100000];
int main() {
	/*
		int a, b;
		cin >> a;
		cin >> b;
		if (a <= 5) {
			cout << 0;
		}
		else if (a <= 12) {
			cout << b / 2;
		}else{
			cout << b;
		}

		return 0;
		*/
		//B
		/*long long int r, d, x;
		cin >> r;
		cin >> d;
		cin >> x;

		int i;
		for (i = 0; i < 10; i++) {
			x = r * x - d;
			cout << x;
			cout <<'\n';
		}


		return 0;*/
		//C
		/*int n, m;
		int l, r;
		cin >> n;
		cin >> m;

		int lmax, rmin;
		lmax = 1;
		rmin = n;
		int i;
		for (i = 0; i < m; i++) {
			cin >> l;
			cin >> r;
			if (l > lmax) {
				lmax = l;
			}
			if (r < rmin) {
				rmin = r;
			}
		}
		if (lmax <= rmin) {
			cout << (rmin - lmax + 1);
		}
		else {
			cout << 0;
		}

		return 0;*/

		//D
	int n, m;
	cin >> n;
	cin >> m;
	int i;
	int a[100000];
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	margesort(a, n, 0, n - 1);


	for (i = 0; i < m; i++) {
		cin >> b[i];
		cin >> c[i];

	}
	margesortD(c, b, m, 0, m - 1);
	//sort(b.begin(), b.end());

	long long int d;
	d = 0;
	int j, k, flag;
	i = 0;
	j = m - 1;
	flag = 0;
	while (flag == 0) {
		for (k = i; k < i + b[j]; k++) {
			if (a[k] < c[j]) {
				a[k] = c[j];
				
			}
			else {
				flag = 1;
			}
			if (k == n) {
				flag = 1;
				break;
			}
		}
		i = i + b[j];
		j--;
		if (j == -1) { flag = -1; }
	}
	for (i = 0; i < n; i++) {
		d = d + a[i];
	}
	cout << d;

	return 0;
	
	
	//E
	/*long long int n, m, k;
	cin >> n;
	cin >> m;
	cin >> k;
	long long int p;
	p= 1000000007
	//2駒総コストを求める.

	//それを(nm-2)C(k-2)倍する.
	*/

}
void margesort(int a[], int a_len, int left, int right)
{
	int i, j, mid, L, R;

	if (right <= left)
		return;

	mid = (left + right) / 2;
	margesort(a, mid, left, mid);
	margesort(a, a_len - mid, mid+1, right);

	for (i = left; i <= mid; i++)
		temp[i] = a[i];
	for (i = mid+1, j = right; i <= right; i++, j--)
		temp[i] = a[j];

	L = left;
	R = right;

	for (i = left; i <= right; i++)
	{
		if (temp[L] <= temp[R])
		{
			a[i] = temp[L];
			L++;
		}
		else
		{
			a[i] = temp[R];
			R--;
		}
	}
}

void margesortD(int a[], int b[], int a_len, int left, int right) {
	int i, j, mid, L, R;

	if (right <= left)
		return;

	mid = (left + right) / 2;
	margesortD(a, b, mid, left, mid);
	margesortD(a, b, a_len - mid, mid+1, right);

	for (i = left; i <= mid; i++) {
		temp[i] = a[i];
		tempb[i] = b[i];
	}
	for (i = mid+1, j = right; i <= right; i++, j--) {
		temp[i] = a[j];
		tempb[i] = b[j];
	}

	L = left;
	R = right;

	for (i = left; i <= right; i++)
	{
		if (temp[L] <= temp[R])
		{
			a[i] = temp[L];
			b[i] = tempb[L];
			L++;
		}
		else
		{
			a[i] = temp[R];
			b[i] = tempb[R];
			R--;
		}
	}
}

Measured memory_bytes: 2176
// ABC145-D
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}
ll mod=pow(10,9)+7;
ll modpow(ll x,ll y,ll mod){ //x^y
    if(y==0) return 1;
    if(y==1) return x%mod;
    if(y%2==1) return x*modpow(x,y-1,mod)%mod;
    ll t=modpow(x,y/2,mod);
    return (t*t)%mod;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    ll x,y;
    cin>>x>>y;
    if((x+y)%3!=0) cout<<0<<endl;
    else{
        if(0<=(2*y-x) and 0<=(2*x-y)){
            ll a=(2*y-x)/3;
            ll b=(2*x-y)/3;
            ll npa=1;
            if(b<a); swap(a,b); //aを小さく 
            for(int i=0;i<a;i++){
                npa=npa*(a+b-i)%mod;
            }
            ll facta=1;
            for(int i=1;i<=a;i++){
                facta=facta*i%mod;
            }
            ll invfacta=modpow(facta,mod-2,mod);
            ll ans=npa*invfacta%mod;
            cout<<ans<<endl;
        }else cout<<0<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
//i64 mod = 998244353;
int int_max = 2147483647;
i64 INF = 1e16;
int max_n = 1e5;

int main(int argc, char **argv) {
    string s, t;
    cin >> s >> t;
    i64 ans{0};
    for (size_t i=0; i<s.size(); ++i) {
        if (s[i] != t[i]) ++ans;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3920
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;


int main()
{
    int n, a, b;
    string s;
    while(cin >> n >> a >> b) {
        cin >> s;
        int a_num = 0, b_num = 0;
        int rk = 0;
        for(int i = 0; i < s.size(); ++ i) {
            //if(s[i] != 'c') rk ++;
            if(s[i] == 'a' && rk < a + b) {
                rk ++;
                a_num ++;
                cout << "Yes" << endl;
            }
            else if(s[i] == 'b' && rk < a + b && b_num < b) {
                rk ++;
                cout << "Yes" << endl;
                b_num ++;
            }
            else cout << "No" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int>B(n-1),A(n);
    long long ans = 0;

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

    ans += B[0];

    for(int j = 0; j < n - 2; j++){
        if(B[j] > B[j+1]){
            B[j] = B[j+1];
        }
    }

    for(int i = 0; i < n-1; i++){
        ans += B[i];
    }
    
    cout << ans << endl;

}

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

int main() {
	int n;
	cin >> n;
	rep(i, 25)rep(j, 15) {
		if (n == i * 4 + j * 7) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
import math

s=int(input())

if __name__=="__main__":
    if s==10**18:
        print(0,0,1000000000,0,0,1000000000)
    else:
        max_x=np.sqrt(s)
        keta=len(str(s))
        sita=(s//(10**(keta//2))+1)*(10**(keta//2))-s

        print(0, 0, s//(10**(keta//2))+1, sita, 1, 10**(keta//2))


Measured memory_bytes: 21512
import math
from functools import reduce
k = int(input())


def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for i in range(1,k+1):
  for j in range(i,k+1):
    for m in range(j,k+1):
      tem=[]
      tem = [i,j,m]
      
      if  len(set(tem)) == 1 :
        ans += i
      elif len(set(tem)) == 2:
        ans += gcd(i,j,m) * 3
      elif len(set(tem)) == 3:
        ans += gcd(i,j,m) * 6

print(ans)




Measured memory_bytes: 69792
import math
A, B, N = map(int, input().split())

if N < B:
    if N % B == 0:
        x = N-1
    else:
        x = N

else:
    if N % B == 0:
        x = B-1
    else:
        x = B-1

ans = math.modf((x/B))[0]*A
print(int(ans))

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,M;
map<int,int> D,T;

int main()
{
	scanf("%d",&N);
	FOR(i,0,N){
		int a;
		scanf("%d",&a);
		D [a]++;
	}
	scanf("%d",&M);
	FOR(i,0,M){
		int a;
		scanf("%d",&a);
		T [a]++;
	}

	bool ans = true;
	for(const auto& it : T){
		ans &= it.second <= D [it.first];
	}
	puts(ans ? "YES" : "NO");

	return 0;
}


Measured memory_bytes: 18944
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn to_int(s: &str) -> usize {
    let v = s.split(":")
        .map(|x| usize::from_str_radix(x, 10).unwrap())
        .collect::<Vec<_>>();
    let (h, m, s) = (v[0], v[1], v[2]);
    h * 3600 + m * 60 + s
}

fn main() {
    loop {
        let n = read::<usize>();
        if n == 0 {
            break;
        }
        let mut imos = vec![0; 24 * 3600];
        for i in 0..n {
            let ss = read_vec::<String>();
            let enter = to_int(&ss[0]);
            let exit = to_int(&ss[1]);
            imos[enter] += 1;
            imos[exit] -= 1;
        }
        let mut summed = vec![0; 24 * 3600];
        summed[0] = imos[0];
        for i in 1..24 * 3600 {
            summed[i] = summed[i - 1] + imos[i];
        }
        println!("{}", summed.iter().max().unwrap());
    }
}

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: 5048
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    ll cnt1=0;
    rep(i,n){
        repi(j,i+1,n) if(a[i]>a[j]) cnt1++;
    }
    ll ans=(cnt1*k)%mod;
    ll cnb=k*(k-1)/2%mod;
    rep(i,n){
        ll cnt2=0;
        rep(j,n) if(a[i]>a[j]) cnt2++;
        ll t=cnt2*cnb%mod;
        ans=(ans+t)%mod;
    }
    cout<<ans;
}

Measured memory_bytes: 3596
import java.util.*;
public class Main {
  public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n=sc.nextInt(),sum=0;
			if(n==0) break;
			for(int i=0;i<n/4;++i){
				sum+=sc.nextInt();
			}
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 18140
#include<bits/stdc++.h>
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int, int>
#define vi              vector<int>
#define si              set<int>
#define usi             unordered_set<int>
#define mii             map<int, int>
#define umii            unordered_map<int, int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int, vi, greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define endl            '\n'
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(t)            int t; cin>>t; while(t--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void jaiswal_sahil()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
}

const int N = 1e6;
int dp[N];
int n;

// top down Approach
int minCost(int i, int *a){

    if(i >= n-1)
        return 0;

    if(dp[i] != -1)
        return dp[i];

    int q1 = inf, q2 = inf;
    if(i+1 < n)
        q1 = abs(a[i] - a[i+1]) + minCost(i+1, a);
        
    if(i+2 < n)
        q2 = abs(a[i] - a[i+2]) + minCost(i+2, a);
    
    return dp[i] = min(q1, q2);

}

// bottom up Approach
int minCostBU(int n, int *a){

    memset(dp, 0, sizeof(dp));
    dp[2] = abs(a[0] - a[1]);
    for(int i=3; i<=n; i++){
        dp[i] = min(abs(a[i-1] - a[i-2]) + dp[i-1], abs(a[i-1] - a[i-3]) + dp[i-2]);
    }
    return dp[n];

}

int32_t main()
{
    jaiswal_sahil();

    cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    
    // memset(dp, -1, sizeof(dp));
    // int ans = minCost(0, a);

    int ans = minCostBU(n, a);
    cout<<ans<<endl;
    return 0;

}

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

int main(){
    int N,K;
    cin >> N >> K;
    int h[N];
    for(int i=0;i<N;i++){
        cin >> h[i];
    }
    sort(h,h+N);
 //   cout << (h[N-1] - h[(N-1)-(K-1)]) << endl;
    int sum=0;
    int min = 0;
    for(int i=0;i<=(N-K);i++){
 //       cout << h[i] << "--" << h[K] <<endl;
        sum =h[i+K-1] - h[i];
        if(i == 0){
            min = sum;
        }
        if(min > sum) min = sum;
//        cout << sum << endl;
        sum = 0;
    }
    cout << min << endl;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, x);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

int lcm(int a, int b) { return a * b / gcd(a, b); }

int main(void) {
  int a, b, c;
  cin >> a >> b >> c;
  ((c >= a && c <= b) ? (cout << "Yes" << endl) : (cout << "No" << endl));
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
 
template <uint MD> struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v(0) {}
    ModInt(ll _v) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<TEN(9) + 7>;
 
const int MF = TEN(6) + TEN(5);
V<Mint> fact(MF + 1), iFac(MF + 1);
void first() {
    fact[0] = 1;
    for (int i = 1; i <= MF; i++) fact[i] = fact[i-1] * Mint(i);
    iFac[MF] = fact[MF].inv();
    for (int i = MF; i >= 1; i--) iFac[i-1] = iFac[i] * Mint(i);
    assert((fact[114] * iFac[114]).v == 1);
}
 
Mint C(int n, int k) {
    if (n < k || n < 0) return Mint(0);
    return fact[n] * iFac[k] * iFac[n - k];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int h, w;
    cin >> h >> w;
    VV<Mint> dp(h, V<Mint>(w)); dp[0][0] = Mint(1);
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            if (s[j] == '#') continue;
            if (i) dp[i][j] += dp[i-1][j];
            if (j) dp[i][j] += dp[i][j-1];
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <sstream>
#include <algorithm>
#include <cmath>

using namespace std;

#if 0 //@@@ 19
int Task3_0()
{
	int N = 0;
	cin >> N;
	vector<int> vctX;
	multimap<int, int> mapN;

	long long sum = 0;
	for (int i = 0; i < N; ++i) {
		int n = 0;
		cin >> n;
		mapN.insert(i, n);
		vctX.push_back(n);
	}

	int cent1Value = *(mapN.begin() + (N / 2));
	int cent2Value = *(mapN.begin() + (N / 2  + 1));

	for (int i = 0; i < N; ++i) {
		int curValue = vctX[i];
		if (curValue >= cent1Value) {
			cout << cent1Value;
		}
		else {
			cout << cent2Value;

		}
	}

	return 0;
}
#endif
class XV {
public:
	XV()
		: value_(0)
		, index_(0)
	{};

	XV(int value, int index)
		: value_(value)
		, index_(index)
	{};
	bool operator < (const XV& another) const
	{
		return value_ < another.value_;
	}

	int value_;
	int index_;

}
;
int main()
{
	int N = 0;
	cin >> N;
	vector<int> vctX(N);
	vector<XV> vctXv(N);
//	multimap<int, int> mapN;

	//long long sum = 0;
	for (int i = 0; i < N; ++i) {
		int n = 0;
		cin >> n;
		vctX[i] = n;
		vctXv[i] = XV(n, i);
	}

	sort(vctXv.begin(), vctXv.end());

	int cent1Value = (vctXv.begin() + (N / 2-1))->value_;
	int cent2Value = (vctXv.begin() + (N / 2))->value_;

	for (int i = 0; i < N; ++i) {
		int curValue = vctX[i];
		if (curValue >= cent2Value) {
			cout << cent1Value << endl;
		}
		else {
			cout << cent2Value << endl;

		}
	}

	return 0;
}

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

int main()
{
    vector<int> time(3);
    rep(i, 3) cin >> time[i];
    sort(all(time));
    cout << accumulate(all(time), 0) - time[2] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

struct Nodes {
    int K1, K2, P;
    Nodes(){}
    Nodes(int K1):K1(K1*3),K2(K1*3+1),P(K1*3+2){}
};

vector<vector<int>> g(333333);

void bfs(vector<ll> &dp, int s) {
    queue<P> q;
    dp[s] = 0;
    q.push(P(0,s));

    while (!q.empty()) {
        P p = q.front(); q.pop();
        int v = p.second;
        for (auto &&e: g[v]) {
            if (dp[e] > dp[v]+1) {
                dp[e] = dp[v]+1;
                q.push(P(dp[e], e));
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    int n,m,s,t;
    cin >> n >> m;
    REP(i,m) {
        int u,v;
        cin >> u >> v;
        --u,--v;
        Nodes U(u); Nodes V(v);
        // K1 -> K2
        g[U.K1].push_back(V.K2);
        // K2 -> P
        g[U.K2].push_back(V.P);
        // P -> K1
        g[U.P].push_back(V.K1);
    }
    cin >> s >> t;
    --s,--t;
    Nodes S(s); Nodes T(t);
    vector<ll> dp(333333, LINF);
    bfs(dp,S.P);

    (dp[T.P]%3 == 0) ? cout << dp[T.P]/3 << endl : cout << -1 << endl;
    return 0;
}

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

const int MAX = 1e+5;
int N, M;
int a[MAX], b[MAX];
map<int, int> mp;

int main() {
  // 入力
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    cin >> a[i] >> b[i];
    mp[a[i]]++;
    mp[b[i]]++;
  }
  map<int, int>::iterator it;
  bool flag = true;
  for (it = mp.begin(); it != mp.end(); it++) {
    if (flag && it->second & 1) flag = false;
  }
  // 解答
  if (flag) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

int main(){
    ll h,w;
    cin>>h>>w;
    vector<string> board(h);
    rep(i,h) cin>>board[i];
    rep(i,h){
        rep(j,w){
            if(board[i][j]=='#'){
                ll cnt=0;
                rep(k,4){
                    ll x=j+dx[k],y=i+dy[k];
                    if(x<0||x>=w||y<0||y>=h||board[y][x]=='.') cnt++;
                }
                if(cnt==4){
                    cout<<"No"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int n,r,i,j,p,c;
int a[100],b[100];

int main(){
  while(1){
    scanf("%d %d",&n,&r);
    if(n==0&&r==0)break;
    
    for(i=0;i<n;i++){
      a[i]=n-i;
    }
    
    for(i=0;i<r;i++){
      
      for(j=0;j<n;j++){
        b[j]=a[j];
      }
      scanf("%d %d",&p,&c);

      for(j=0;j<c;j++){
        a[j]=b[p-1+j];
      }
      
      for(j=c;j<c+p-1;j++){
        a[j]=b[j-c];
      }
    }
    printf("%d\n",a[0]);
  }
  return 0;
}

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

using namespace std;

long long n, ans;

int main() {
	scanf("%lld", &n);
	if (n == 0) {
		puts("0");
	} else {
		n--;
		ans++;
		ans += n % 3;
		n /= 3;
		while (n) {
			long long tmp = min(2LL, n);
			n -= tmp;
			ans += tmp;
			ans += n % 3;
			n /= 3;
		}
		printf("%lld\n", ans);
	}
}


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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N, M;
signed main() {
    cin >> N >> M;
    int ans = 0;
    for (int i = 1; i <= (int)sqrt(M); i++) {
        if (M % i == 0) {
            if (M / i >= N) {
                ans = max(ans, i);
            }
            if (i >= N) {
                ans = max(ans, M / i);
            }

        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long sum[100100];
long long possum[100100];
int a;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a;
		sum[i]=sum[i-1]+a;
		possum[i]=possum[i-1];
		if(a>0)
			possum[i]+=a;
	}
	long long ans=sum[n];
	for(int i=1;i<=n-k+1;i++){
		long long s1=possum[i-1];
		long long s2=possum[n]-possum[i+k-1];
		ans=max(ans,s1+s2);
		ans=max(ans,s1+s2+sum[i+k-1]-sum[i-1]);
	}
	cout<<ans<<endl;
	return 0;
}


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

#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

int r[4000];
int g[4000];
int b[4000];

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    for(int i = 0; i < n; i++){
        if(s[i] == 'R')
            r[i]++;
        if(s[i] == 'G')
            g[i]++;
        if(s[i] == 'B')
            b[i]++;
    
        if(i > 0){
            r[i] += r[i-1];
            g[i] += g[i-1];
            b[i] += b[i-1];
        }
    }

    ll cnt = 0;
    for(int i = 0; i < n; i++){
        char curr = s[i];
        for(int j = i; j < n; j++){
            if(s[j] != curr){
                if(curr == 'R'){
                    if(s[j] == 'G'){
                        cnt += b[n-1] - b[j];
                        if(j + j - i < n && s[j + j - i] == 'B')
                            cnt--;    
                    }
                    if(s[j] == 'B'){
                        cnt += g[n-1] - g[j];
                        if(j + j - i < n && s[j + j - i] == 'G')
                            cnt--;
                    }
                }
                if(curr == 'G'){
                    if(s[j] == 'R'){
                        cnt += b[n-1] - b[j];
                        if(j + j - i < n && s[j + j - i] == 'B')
                            cnt--;
                    }
                    if(s[j] == 'B'){
                        cnt += r[n-1] - r[j];
                        if(j + j - i < n && s[j + j - i] == 'R')
                            cnt--;
                    }
                }
                if(curr == 'B'){
                    if(s[j] == 'R'){
                        cnt += g[n-1] - g[j];
                        if(j + j - i < n && s[j + j - i] == 'G')
                            cnt--;
                    }
                    if(s[j] == 'G'){
                        cnt += r[n-1] - r[j];
                        if(j + j - i < n && s[j + j - i] == 'R')
                            cnt--;
                    }
                }
            }
        }
    }
    cout << cnt;
}

Measured memory_bytes: 3664
S = list(input())
S.sort()

tmp = S[0]
if tmp != 'a':
    print('a')
    exit()

for i in S:
    if ord(i) == (ord(tmp) + 1) or ord(i) == ord(tmp):
        tmp = i
    else:
        print(chr(ord(i)-1))
        exit()

if tmp == 'z':
    print("None")
else:
    print(chr(ord(i)+1))

Measured memory_bytes: 50160
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 5432
 
class Union_Find{
public:
    int par[MAX],rank[MAX];
    Union_Find(int N){
	for(int i = 0 ; i < N ; i++){
	    par[i] = i;
	    rank[i] = 0;
	}
    }
 
    int find(int x){
	if(par[x] == x){
	    return x;
	}
	return par[x] = find(par[x]);
    }
 
    void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(rank[x] < rank[y]){
	    par[x] = y;
	}else{
	    par[y] = x;
	    if(rank[x] == rank[y]){
		rank[x]++;
	    }
	}
    }
 
    bool same(int x,int y){
	return find(x) == find(y);
    }
};
 
int main(){
    int N,M,x[MAX];
    string a[MAX],s,t;
    map<string,int> mp;
    cin >> N;
    for(int i = 0 ; i < N ; i++){
	cin >> a[i] >> x[i];
	mp[a[i]] = i;
    }
    Union_Find uf(N);
    cin >> M;
    while(M--){
	cin >> s >> t;
	uf.unite(mp[s],mp[t]);
    }
    int res = 0;
    for(int i = 0 ; i < N ; i++){
	int min = (1<<29);
	for(int j = 0 ; j < N ; j++){
	    if(uf.same(i,j)){
		min = std::min(min,x[j]);
	    }
	}
	res += min;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define ff first
#define ss second
#define p pair<ll,ll>
#define pb push_back
#define endl '\n'
#define w(t) ll test;cin>>test;while(test--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define iof  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define pi acos(-1)
const int mxn=1e9+5;
int main()
{
    fast;
    ll n;
    cin>>n;
    vector<ll>vec(n);
    for(auto &i:vec)
    {
        cin>>i;

    }
    ll cnt=0;
    sort(vec.begin(),vec.end());
    ll ans=0;
    for(ll i=0;i<n;i++)
    {

        for(ll j=i+1;j<n;j++)
        {
            if(vec[j]==vec[i])continue;
            ll sum=vec[i];
            sum+=(ll)vec[j];
            for(ll k=j+1;k<n;k++)
            {
                if(vec[k]<sum&&vec[k]!=vec[i]&&vec[k]!=vec[j])
                  {
                       ans++;
                  }
            }
        }
    }
    cout<<ans<<endl;
}




Measured memory_bytes: 3652
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> L(N);
	for (int i = 0; i < N; ++i) cin >> L[i];
	vector<int> S(N + 1);
	for (int i = 0; i < N; ++i) S[i + 1] = S[i] + L[i];
	vector<int> lens;
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < i; ++j) {
			lens.push_back(S[i] - S[j]);
		}
	}
	sort(lens.begin(), lens.end());
	lens.erase(unique(lens.begin(), lens.end()), lens.end());
	int ans = lens.back();
	for (int i : lens) {
		if (i == lens.back()) continue;
		vector<int> dp(N + 1, -1); dp[0] = i;
		for (int j = 1; j <= N; ++j) {
			for (int k = 0; k < j; ++k) {
				if (S[j] - S[k] <= i) {
					dp[j] = max(dp[j], min(dp[k], S[j] - S[k]));
				}
			}
		}
		if (dp[N] != -1) ans = min(ans, i - dp[N]);
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<LL,LL>
#define LL long long
using namespace std;

int main () {
    //clock_t start = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    LL n,k;
    cin >> n >> k;
    LL a[n+5];
    for (LL i=1;i<=n;i++) cin >> a[i];
    LL b[n+5];
    for (LL i=1;i<=n;i++) cin >> b[i];
    sort (a+1,a+n+1);
    reverse(a+1,a+n+1);
    sort (b+1,b+n+1);
    LL l = 0, h = 1e18, ans = 1e18;
    while (l <= h) {
        LL m = (l+h)/2;
        LL p = k;
        for (LL i=1;i<=n;i++) {
            if (a[i]*b[i] > m) {
                p -= (a[i]*b[i] - m + b[i] - 1) / b[i];
            }
        }
        if (p >= 0) {
            ans = m;
            h = m-1;
        } else {
            l = m+1;
        }
    }
    cout << ans << endl;
    //cerr << fixed << setprecision(3) << (clock()-start)*1./CLOCKS_PER_SEC << endl;
    return 0;
}

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

class Node {
  public:
    vector<int> edge;
    bool is_visited;
    Node()
    {
      is_visited = false;
    }
};

class Edge {
  public:
    int a;
    int b;
    int color;
    Edge()
    {
      a = -1;
      b = -1;
      color = 0;
    }
    Edge(int _a, int _b)
    {
      a = _a;
      b = _b;
      color = 0;
    }
};

void dfs(vector<Node>& graph, vector<Edge>& edge, int idx)
{
  if (graph.at(idx).is_visited) {
    return;
  }
  graph.at(idx).is_visited = true;
  int inuse = 0;
  for (int e : graph.at(idx).edge) {
    if (edge.at(e).color != 0) {
      inuse = edge.at(e).color;
      break;
    }
  }
  int cnt = 1;
  for (int e : graph.at(idx).edge) {
    if (cnt == inuse) {
      cnt++;
    }
    if (edge.at(e).color != 0) {
      continue;
    }
    edge.at(e).color = cnt++;
    int to;
    if (edge.at(e).a == idx) {
      to = edge.at(e).b;
    } else {
      to = edge.at(e).a;
    }
    dfs(graph, edge, to);
  }
}

int main()
{
  int n;
  cin >> n;
  vector<Node> graph(n);
  vector<Edge> edge(n-1);
  for (int i = 0; i < n-1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge.at(i).a = a;
    edge.at(i).b = b;
    graph.at(a).edge.push_back(i);
    graph.at(b).edge.push_back(i);
  }

  int k = 0;
  for (const auto& n : graph) {
    k = max(k, (int)n.edge.size());
  }

  dfs(graph, edge, 0);

  cout << k << '\n';
  for (const auto& e : edge) {
    cout << e.color << '\n';
  }

  return 0;
}


Measured memory_bytes: 10112
#include <iostream>
#include<set>
#include<math.h>
#include<list>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
 
int main(){
    long D, N;
    cin >> D >> N;
 
    if(N==100){
        cout << (int)(101 * pow(100, D)) << endl;
    }else{
        cout << (int)(N * pow(100, D)) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

const int MAX_N = 2e5 + 5;

int n;
ll X;
ll arr [MAX_N];

ll score (ll k) {
  // we do k trips
  ll ans = 0;
  ll cur = 3, curc = 0;
  for (int i = n - 1; i >= 0; i--) {
    ans += (cur == 3 ? 5 * arr[i] : cur * arr[i]);
    curc++;
    if (curc == k) {
      curc = 0;
      cur += 2;
    }
  }

  return ans + k * X;
}

int main () {
  cin >> n >> X;

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

  int ansk = 0; // the greatest n such that score(n) >= score(n + 1)
  for (int k = 1 << 20; k != 0; k /= 2) {
    if (score(ansk + k) >= score(ansk + k + 1)) {
      ansk += k;
    }
  }

  //  cerr << ansk + 1 << endl;
  cout << n * X + score(ansk + 1) << endl;
}


Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPS(i, a, b) for (int i = (a); i < (b); i++)
using namespace std;
using ll = long long;

int main() {
  int n;
  cin >> n;
  ll a[n],b[n],c[n],dp[10000000][3];
  vector<bool> a_checked(10000000,true);
  vector<bool> b_checked(10000000,true);
  vector<bool> c_checked(10000000,true);
  
  REP(i,n){
    cin >> a[i] >> b[i] >> c[i];
  }

  dp[0][0] = 0;
  dp[0][1] = 0;
  dp[0][2] = 0;
  REP(i,n+100){
      dp[i+1][0] = max(dp[i][1],dp[i][2]) + a[i];
    
      dp[i+1][1] = max(dp[i][0],dp[i][2]) + b[i];
    
      dp[i+1][2] = max(dp[i][1],dp[i][0]) + c[i];
    
  }
      
  
  
  cout << max({ dp[n][0] , dp[n][1] , dp[n][2]}) << endl;
}


Measured memory_bytes: 11664
fun main(args: Array<String>) = ripPro0408c()

fun ripPro0408c() {
    val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    val hList = readLine()!!.split(' ').map { it.toLong() }

    val answer = hList.sortedDescending().drop(k).sum()

    println(answer)
}


Measured memory_bytes: 83248
#include <iostream>
#include <stdio.h>

int gcd(int a, int b) {
    int c = a % b;
    if (c == 0) {
        return b;
    }
    return gcd(b, c);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    
    printf("%d\n", gcd(a, b));
    
    return 0;
}

Measured memory_bytes: 3180
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>

using namespace std;

typedef long long int ll; 
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

void floatOutPutSetup(){
    cout << fixed;
    cout << setprecision(10);
}

int main(){
    int N,K,ans;
    cin >>N>>K;
    ans =0;
    while(N!=0){
        ans++;
        N /= K;
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
template<class T>inline T cabs(T x){return x>=0?x:-x;}
const int N=200010;
const lint LINF=0x7f7f7f7f7f7f7f7fll;
lint val[N];
namespace seg{
	struct Node;
	typedef Node* node;
	struct Node{
		node lson,rson;
		int l,m,r;
		lint val[2];
		inline void up(){
			val[0]=min(lson->val[0],rson->val[0]);
			val[1]=min(lson->val[1],rson->val[1]);
		}
	}*rt;
	node build(int l,int r){
		static node n=new Node[N<<1];
		node x=n++;
		x->l=l,x->m=(l+r)>>1,x->r=r;
		memset(x->val,127,sizeof(x->val));
		if(l!=r){
			x->lson=build(l,x->m);
			x->rson=build(x->m+1,r);
		}
		return x;
	}
	lint ask(node x,int l,int r,int d){
		if(x->l==l&&x->r==r)return x->val[d];
		if(r<=x->m)return ask(x->lson,l,r,d);
		if(l>x->m)return ask(x->rson,l,r,d);
		return min(ask(x->lson,l,x->m,d),ask(x->rson,x->m+1,r,d));
	}
	void set(node x,int p,lint v){
		if(x->l==x->r){
			val[p]=v;
			x->val[0]=v+p;
			x->val[1]=v-p;
		}else{
			set(p<=x->m?x->lson:x->rson,p,v);
			x->up();
		}
	}
}
int main(){
	int n=ni,tot=ni,last=ni;
	lint delta=0;
	memset(val,127,sizeof(val));
	seg::set(seg::rt=seg::build(1,n),ni,0);
	while(tot--){
		using namespace seg;
		int cur=ni;
		lint val=min(ask(rt,1,cur,1)+cur,ask(rt,cur,n,0)-cur)+delta;
		delta+=cabs(cur-last);
		if(val<(::val[cur]+delta)){
			set(rt,last,val-delta);
		}
		last=cur;
	}
	lint ans=LINF;
	for(int i=1;i<=n;i++){
		apmin(ans,val[i]);
	}
	printf("%lld\n",ans+delta);
	return 0;
}

Measured memory_bytes: 20608
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

happiness = sum(B);
last = -1
for i in range(n-1):
    if A[i+1] - A[i] == 1:
        happiness += C[A[i]-1]

print(happiness)



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

int h, w, a, b;
int main()
{
	int i, j;
	cin >> h >> w >> a >> b;
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			printf("%d", (i < b) ^ (j < a));
		}
		puts("");
	}
    return 0;
}

Measured memory_bytes: 1280
n = int(input())
h = list(map(int, input().split()))


def cost(x: int, y: int) -> int:
    global h
    return abs(h[x] - h[y])


dp = [0] * n
dp[0], dp[1] = 0, cost(0, 1)

for i in range(2, n):
    dp[i] = min(dp[i - 1] + cost(i, i - 1), dp[i - 2] + cost(i, i - 2))

print(dp[n - 1])


Measured memory_bytes: 20572
#include <iostream>
#include <vector>
#include <utility>

using namespace std;
typedef pair<int, int> P;

int H, W;
char map[55][55];
int memo[55][55][55][55];
vector<P> vec[26];

int calc(int sx, int sy, int tx, int ty)
{
	if(memo[sx][sy][tx][ty] != -2) return memo[sx][sy][tx][ty];
	if(sx > tx || sy > ty) return -1;
	if(map[sx][sy] == '#' || map[tx][ty] == '#') return -1;
	if(sx == tx && sy == ty) return 0;
	
	int ret = -1;
	if(map[sx][sy] >= 'a' && map[sx][sy] <= 'z'){
		int idx = map[sx][sy] - 'a';
		for(int i = 0; i < vec[idx].size(); i++){
			int tmp = -1, tmp2 = -1, nx = vec[idx][i].first, ny = vec[idx][i].second;
			if( (sx == nx && sy+1 == ny) || (sx+1 == nx && sy == ny) ) tmp = 0;
			else{
				if(sx < W && nx > 1) tmp = max(tmp, calc(sx+1, sy, nx-1, ny));
				if(sy < H && nx > 1) tmp = max(tmp, calc(sx, sy+1, nx-1, ny));
				if(sx < W && ny > 1) tmp = max(tmp, calc(sx+1, sy, nx, ny-1));
				if(sy < H && ny > 1) tmp = max(tmp, calc(sx, sy+1, nx, ny-1));
				if(tmp == -1) continue;
			}
			if(nx == tx && ny == ty) tmp2 = 0;
			else{
				if(nx < W) tmp2 = max(tmp2, calc(nx+1, ny, tx, ty));
				if(ny < H) tmp2 = max(tmp2, calc(nx, ny+1, tx, ty));
				if(tmp2 == -1) continue;
			}
			ret = max(ret, tmp + tmp2 + 1);
		}
	}
	if(sx < W) ret = max(ret, calc(sx+1, sy, tx, ty));
	if(sy < H) ret = max(ret, calc(sx, sy+1, tx, ty));
	
	return memo[sx][sy][tx][ty] = ret;
}

int main(void)
{
	while(1){
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		
		for(int i = 0; i < 26; i++) vec[i].clear();
		for(int y = 1; y <= H; y++){
			for(int x = 1; x <= W; x++){
				cin >> map[x][y];
				if(map[x][y] >= 'A' && map[x][y] <= 'Z'){
					vec[map[x][y] - 'A'].push_back(make_pair(x, y));
				}
			}
		}
		
		for(int sx = 1; sx <= W; sx++){
			for(int sy = 1; sy <= H; sy++){
				for(int tx = 1; tx <= W; tx++){
					for(int ty = 1; ty <= H; ty++){
						memo[sx][sy][tx][ty] = -2;
					}
				}
			}
		}
		cout << calc(1, 1, W, H) << endl;
	}
	
	return 0;
}


Measured memory_bytes: 32784
#include<stdio.h>

int main(){
	int N;
	int c1=0,c2=0,c3=0,c4=0;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		char msg[5];
		scanf("%s", msg);
		if(msg[0]=='A'){
			c1++;
		}
		else if(msg[0]=='W'){
			c2++;
		}
		else if(msg[0]=='T'){
			c3++;
		}
		else{
			c4++;
		}
	}
	printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n", c1, c2, c3, c4);
	return 0;
}

Measured memory_bytes: 3200
N = int(input())
sum = 0
for i in range(N):
  n = i+1
  if n%3 == 0:
    a = 'Fizz'
    continue
  elif n%5 == 0:
    a = 'Buzz'
    continue
  else :
    a = n
  sum = sum + a
print(sum)

Measured memory_bytes: 9024
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		char[] w = sc.next().toCharArray();
		sc.close();
		int[] c = new int[26];
		for (i = 0; i < w.length; i++) {
			c[w[i]-'a']++;
		}
		boolean f = true;
		for (i = 0; i < c.length; i++) {
			if(c[i]%2==1) {
				f=false;
				break;
			}
		}
		out.println(f?"Yes":"No");
	}
}


Measured memory_bytes: 21844
import java.util.*;
 
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
         
        while(h != 0 || w != 0){
 
            StringBuilder sb = new StringBuilder();
 
            for(int i = 0; i < h; i++){
 
                for(int j = 0; j < w; j++){
                    if(j == 0 || j == w - 1 || i == 0 || i == h - 1){
                        sb.append("#");
                    }else{
                        sb.append(".");
                    }
                }
                sb.append("\n");
 
            }
            System.out.println(sb);
 
            h = sc.nextInt();
            w = sc.nextInt();
        }
    }
}

Measured memory_bytes: 20496
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main(void){

  int i,N,max=0,a=0;
  scanf("%d",&N);
  int l[N];
  
   for(i=0;i<N;i++){
     scanf("%d",&l[i]);
     if(max<=l[i]){
       max=l[i];
     }
     a+=l[i];
   }
  if(a>2*max)
     printf("Yes\n");
  else
    printf("No");
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

#define rep(i, e) for (int i = 0; i < e; i++)
#define repp(i, s, e) for (int i = s; i < e; i++)
#define N_Max 100
#define Card_Max 36
#define ll long long

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

int main()
{
    int h, w, cnt = 0;
    char m[55][55] = {};
    cin >> h >> w;
    rep(i, h) rep(j, w) cin >> m[i][j];
    rep(i, h)
    {
        rep(j, w)
        {
            if(m[i][j] == '.'){
                cnt = 0;
                rep(k, 8)
                {
                    if (i + dy[k] >= 0 && i + dy[k] < h && j + dx[k] >= 0 && j + dx[k] < w)
                    {
                        if (m[i + dy[k]][j + dx[k]] == '#')
                        {
                            cnt++;
                        }
                    }
                }
                m[i][j] = cnt + '0';
            }
        }
    }

    rep(i, h)
    {
        rep(j, w)
        {
            cout << m[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
 
#define MAX 2000
 
int main(){
  int n, i, j, a[20], dp[MAX+1], in;
 
  memset(dp,0,sizeof(dp));
 
  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,a + i);
  }
 
  dp[0] = 1;
  for(i = 0 ; i < n ; i++){
    for(j = MAX ; j >= 0 ; j--){
      if(dp[j] && j + a[i] <= MAX){
        dp[j + a[i]] = 1;
      }
    }
  }
   
  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,&in);
    if(dp[in]){
      puts("yes");
    }else{
      puts("no");
    }
  }
 
  return 0;
}

Measured memory_bytes: 588
import scala.io.StdIn.readInt

object Main {

  def scan(sum:Int,i:Int):Int = {
    if(i==0) sum
    else {
      val n = readInt
      scan(sum+n,i-1)
    }
  }

  def main(args:Array[String]) = {
    val buf = Iterator.continually(readInt).takeWhile(_ != 0).map { n=>
      scan(0,n/4)
    }
    println(buf.mkString("\n"))
  }
}

Measured memory_bytes: 43496