akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 1000000007

ll wf[301][301];

int main(){
	for (int i = 0;i < 301;i++)for (int j = 0;j < 301;j++)wf[i][j] = LLONG_MAX / 3;
	ll N, M, L, a, b, c;
	cin >> N >> M >> L;
	for (int i = 0;i < M;i++) {
		cin >> a >> b >> c;
		a--;b--;
		wf[a][b] = c;
		wf[b][a] = c;
	}
	
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			for (int k = 0;k < N;k++) {
				wf[j][k] = min(wf[j][k], wf[j][i] + wf[i][k]);
			}
		}
	}

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			if (i == j)wf[i][j] = 0;
			else if (wf[i][j] <= L)
				wf[i][j] = 1;
			else
				wf[i][j] = LLONG_MAX / 3;
		}
	}

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			for (int k = 0;k < N;k++) {
				wf[j][k] = min(wf[j][k], wf[j][i] + wf[i][k]);
			}
		}
	}

	int Q, s, t;cin >> Q;
	for (int i = 0;i < Q;i++) {
		cin >> s >> t;
		s--;t--;
		if (wf[s][t] >= LLONG_MAX / 4)cout << -1 << endl;
		else cout << wf[s][t] - 1 << endl;
	}
}

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

#define CIN2(a,b) long long a,b;cin >> a >> b;
#define CIN3(a,b,c) long long a,b,c;cin >> a >> b >> c;
#define CIN4(a,b,c,d) long long a,b,c,d;cin >> a >> b >> c >> d;
#define rep(i,n) for(int i=0,i##_len=(n); i<i##_len; ++i)
#define MAX(p,q)((p)>(q)?(p):(q))
typedef long long lli;

int main(){
    CIN4(x,y,z,k)
    lli a[1000]; rep(i,x) cin >> a[i];
    lli b[1000]; rep(i,y) cin >> b[i];
    lli c[1000]; rep(i,z) cin >> c[i];

    lli ab[1000'000];
    int cnt = 0;
    rep(i,x){
        rep(j,y){
            ab[cnt] = a[i] + b[j];
            cnt++;
        }
    }
    sort(ab, ab+cnt, greater<lli>());

    sort(c, c+z, greater<lli>());
    vector<lli> abc;
    int cnt2 = 0;
    rep(i,k){
        rep(j,z){
            if((i+1)*(j+1)>k) break;
            else abc.push_back(ab[i]+c[j]);
        }
    }
    sort(abc.begin(), abc.end(), greater<lli>());
    rep(i,k) cout << abc[i] << endl;
}


Measured memory_bytes: 8448
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main()
{
   int n,a,b,c;
   scanf("%d %d %d", &a, &b, &c);
   scanf("%d", &n);
   while(b<=a && n!=0)
   {
       b*=2;
       n--;
   }
   while(c<=b && n!=0)
   {
       c*=2;
       n--;
   }
   if(a<b && b<c) printf("Yes");
   else printf("No");
}


Measured memory_bytes: 1732
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/

	coding: utf-8
	lang: C (GCC 5.4.1)
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int n;
	int a[17], x[17][17], y[17][17];
	int ans = 0, temp;
	bool flag;

	scanf("%d",&n);
	for(int i = 0; i < n; ++i){
		scanf("%d",&a[i]);
		for(int j = 0; j < a[i]; ++j){
			scanf("%d%d", &x[i][j], &y[i][j]);
			--x[i][j];
		}
	}

	for(int i = 0; i < (1 << n); ++i){
		flag = true;
		for(int j = 0; j < n; ++j){
			if(i & (1 << j)){
				for(int k = 0; k < a[j]; ++k){
					if(i & (1 << x[j][k])){
						if(y[j][k] == 0)	flag = false;
					}
					else{
						if(y[j][k] == 1)	flag = false;
					}
				}
			}
		}
		if(flag){
			temp = __builtin_popcount(i);
			ans = ans < temp ? temp : ans;
		}
	}
	printf("%d",ans);
	return 0;
}


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

int main(){
  string s;
  cin >> s;
  int n=0;
  if(s=="SSR"||s=="SRS"||s=="RSS"||s=="RSR") cout << 1 << endl;
  else if(s=="SSS") cout << 0 << endl;
  else if(s=="RRS"||s=="SRR") cout << 2 << endl;
  else if(s=="RRR") cout << 3 << endl;
}
  
  
    
    


Measured memory_bytes: 3576
#include <iostream>
using namespace std;
signed main(){
    
  int a,b,c;
  cin>>a>>b>>c;
  if(a==1 && b==1){
    cout<<"Open\n";
  }
  else
    if(c==1){
      cout<<"Open\n";
    }
    else
  if(a==0 && b==0 && c==0){
  cout<<"Close\n";
    }

  
    else{
      cout<<"Close\n";
    }

  



  return(0);
}



Measured memory_bytes: 3088
#include <stdio.h>
 
int main(void){
 
    int W = 0;
    int H = 0;
    int x = 0;
    int y = 0;
    int r = 0;
 
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if ((x - r >= 0) & (x + r <= W) & (y - r >= 0) & (y + r <= H)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

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

using namespace std;

int main()  {

    char s1[51], s2[51], t[51];

    scanf("%s", s1);
    scanf("%s", t);

    bool flag;
    int ind = -1;

    int l1 = strlen(s1);
    int l2 = strlen(t);

    int i, j;

    for(i = 0; i <= l1 - l2; i++) {

        flag = 1;
        int temp = i;
        for(j = 0; j < l2; j++, i++) {

            if(s1[i] != '?' && s1[i] != t[j])   flag = 0;
        }
        i = temp;
        if(flag)    ind = temp;
    }


    if(ind != -1)   {
    for(i = ind, j = 0; i < ind + l2; i++, j++) {

        s1[i] = t[j];
    }

    for(i = 0; i < l1; i++) {

        if(s1[i] == '?')    s1[i] = 'a';
    }

    printf("%s\n", s1);

    }

    else    {

        printf("UNRESTORABLE\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<queue>
#include<tuple>
using namespace std;
typedef long long ll;
//find_by_order, order_of_key
#define forn(i, n) for (ll i=0;i<ll(n);++i)
vector<int> graph[111111];
int dist[111111];
int pre[111111];
void solve()
{
    int n, m; scanf("%d%d", &n, &m);
    forn(i, m)
    {
        int x, y; scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    memset(dist, 0x3F, sizeof dist);
    dist[1] = 0;
    priority_queue<pair<int,int>> pq;
    pq.push({-0, 1});
    while(!pq.empty())
    {
        int d, now; tie(d, now) = pq.top(); pq.pop();
        d*=-1;
        if (d!= dist[now]) continue;
        for (int nxt : graph[now])
        {
            int nc = d + 1;
            if (nc < dist[nxt])
            {
                dist[nxt] = nc;
                pre[nxt] = now;
                pq.push({-dist[nxt], nxt});
            }

        }
    }
    puts("Yes");
    for (int i=2;i<=n;++i) printf("%d\n", pre[i]);
}
int main()
{
    ll T=1;
    while(T--) solve();
    return 0;
}


Measured memory_bytes: 11064
#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
#define db double
using namespace std;
inline ll read(){
	ll res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=1e6+5;
struct Vector{ll v;db t;}q[N];
ll t[N],v[N];
ll n,x,y,L;
ll l,r;
inline void merge(Vector &a,Vector b){
	a.t=(a.t*a.v+b.t*b.v)/(a.v+b.v);
	a.v+=b.v;
}
int main()
{
	n=read();L=read();
	l=1,r=0;
	for(ll i=1;i<=n;i++)
	{
		t[i]=read();v[i]=read();
		while(x+v[i]>L)
		{
			ll del=min(q[l].v,x+v[i]-L);
			q[l].v-=del;
			x-=del,y-=del*q[l].t;
			if(!q[l].v) ++l;
		}
		q[++r].v=v[i];q[r].t=t[i];
		y+=v[i]*t[i],x+=v[i];
		while(l<r && q[r].t<q[r-1].t) merge(q[r-1],q[r]),--r;//和前面温度大的合并，减少损失 
        printf("%lf\n",(db)y/L);
	}
	return 0;
}

Measured memory_bytes: 29056
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
K = INT()
A, B = MAP()
 
for i in range(A, B+1):
	if i % K == 0:
		print("OK")
		exit()
 
print("NG")

Measured memory_bytes: 10048
public class Main{
	public void run(java.io.InputStream in,java.io.PrintStream out){
		java.util.Scanner sc = new java.util.Scanner(in);

/*answer*/
		int N, M;
		int[] b, p;
		int od, ev, ze, i, count;

		N = sc.nextInt();
		M = sc.nextInt();
		b = new int[N];
		p = new int[M];
		od = 0;
		ev = 0;
		ze = 0;
		count = 0;

		for(i = 0;i < N;i++){
			b[i] = sc.nextInt();
			if(b[i] == 0)ze++;
		}
		for(i = 0;i < M;i++){
			p[i] = sc.nextInt();
			if(i % 2 == 0){
				ev += p[i];
			}else{
				od += p[i];
			}
		}
		sc.close();

		if(ev != od){
			if(ev == ze){
				count = zerosort(b, p, N, M);
			}else{
				for(i = 0;i < N;i++){
					b[i] = (b[i] + 1) % 2;
				}
				count = zerosort(b, p, N, M);
			}
		}else{
			count = zerosort(b, p, N, M);
			for(i = 0;i < N;i++){
				b[i] = (b[i] + 1) % 2;
			}
			ze = zerosort(b, p, N, M);
			if(count > ze)count = ze;
		}

		System.out.println(count);

	}
	public static void main(String[] args){
		(new Main()).run(System.in,System.out);
	}

	private static int zerosort(int[] b, int[] p, int N, int M){
		int i, j, k, a, count, xx;
		int[] ans, b2;

		ans = new int[N];
		b2 = new int[N];

		a = 0;
		k = 0;
		count = 0;
		for(i = 0;i < M;i++){
			for(j = 0;j < p[i];j++){
				ans[j + k] = a;
			}
			k += p[i];
			a = (a + 1) % 2;
		}

		for(i = 0;i < N;i++){
			b2[i] = b[i];
		}

		for(i = 0;i < (N - 1);i++){
			for(j = i;j < N;j++){
				if(ans[i] == b2[j]){
					a = b2[i];
					b2[i] = b2[j];
					b2[j] = a;
					count = count + (j - i);
					break;
				}
			}
		}
		return count;
	}
}

Measured memory_bytes: 17376
data = input().split()
N = int(data[0])
L = int(data[1])
taste = []
for i in range(N):
    taste.append(L + (i+1) - 1)
absTaste = []
for i in range(N):
    absTaste.append(abs(taste[i]))
index = 0
minimum = 0
for i in range(1,N):
    if absTaste[i-1] > absTaste[i]:
        index = i
        minimum = taste[i]
ans = sum(taste) - taste[index]#sumはリスト内の数値の合計を計算する関数
print(ans)

Measured memory_bytes: 38384
#include <iostream>
#include <cmath>
using namespace std;
int main() {
  float sum;
  int n;
  while (cin >> n) {
    sum = 100000;
    for (int i = 0; i < n; i++) {
      sum *= 1.05;
      sum = ceil(sum / 1000) * 1000;
    }
    cout << (int)sum << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
 
int rot[5][7] = {
{0,1,2,3,4,5,6},{0,2,6,3,4,1,5},{0,4,2,1,6,5,3},{0,3,2,6,1,5,4},{0,5,1,3,4,6,2}};
int assign[7];      // サイコロの1～6の各面に割り当てる数字
int tr['Z'];
 
void dice_init(int *a)
{
    int i;
    int t[5] = {0,'N','E','W','S'};
    for (i = 1; i <= 6; i++) assign[i] = a[i];
    for (i = 1; i <= 4; i++) tr[t[i]] = i;
}
 
char s[102];
int main()
{
    int i, k1, k2;
    int a[7], dice[2][7];
    char *p;
 
    for (i = 1; i <= 6; i++) scanf("%d", a+i);
    dice_init(a);
    scanf("%s", p=s);
    for (i = 1; i <= 6; i++) dice[0][i] = rot[0][i];
    for (k1 = 0, k2 = 1; *p; k1 = k2, k2 = !k2) {
        for (i = 1; i <= 6; i++) dice[k2][i] = dice[k1][rot[tr[*p]][i]];
        p++;
    }
    printf("%d\n", assign[dice[k1][1]]);
    return 0;
}


Measured memory_bytes: 2092
N, K = gets.chomp.split(" ").map(&:to_i)
1.upto(K) do |i|
  if i > N - K + 1
    puts 0
  else
    blue = (1..i + 1).to_a.repeated_combination(N - K + 1 - i).size
    red = (1..i).to_a.repeated_combination(K - i).size
    ans = blue * red % (10 ** 9 + 7)
    puts ans
  end
end


Measured memory_bytes: 2812
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			int cnt = 0;

			for (int i = 0; i < n; i++) {
				if (i + 1 != sc.nextInt()) {
					cnt++;
				}
			}

			if (cnt <= 2) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}


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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T;
	cin >> T;
	ll arr[100002] = {0};
	ll sum = 0;
	for(int i = 0; i<T;i++)
	{
		int temp;
		cin >>temp;
		sum += temp;
		arr[temp]++;
	}
	int Q;
	cin >>Q;
	while(Q--)
	{
		int B,C;
		cin >>B>>C;
		ll temp = arr[B];
		sum -= B*temp;
		sum += C*temp;
		arr[B] -= temp;
		arr[C] += temp;
		cout << sum<<endl; 
	}
}


Measured memory_bytes: 4372
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int n, k;
	cin >> n >> k;
	vector<int> vec;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	int ans = 0;
	for (int i = 0; i < k; ++i) {
		ans = ans + vec[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

n, T = map(int, input().split())
t = list(map(int, readline().rstrip().split()))
ans = 0
tmp = t[0]
for i in range(1, n):
    if t[i] > t[i-1] + T:
        ans += t[i-1] - tmp + T
        tmp = t[i]
ans += t[n-1] - tmp + T
print(ans)

Measured memory_bytes: 25836
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static MyIO;


public class C
{
	public static void Main()	
	{
		int N = GetInt();
		int A = GetInt();
		int[] x = new int[N+1];
		for(int i = 0; i < N; i++)
			x[i+1] = GetInt();

		long[,,] dp = new long[N+1, N+1, 2501];
		dp[0,0,0] = 1;
		for(int i = 1; i <= N; i++)
		{
			for(int j = 0; j <= N; j++)
			{
				for(int k = 0; k <= 2500; k++)
				{
					dp[i, j, k] += dp[i-1, j, k];
					if(j >= 1 && k >= x[i])
						dp[i, j, k] += dp[i-1, j-1, k-x[i]];
				}
			}
		}

		long ans = 0;
		for(int i = 1; i <= N; i++)
		{
			ans += dp[N, i, A * i];
		}
		Console.WriteLine(ans);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


Measured memory_bytes: 60768
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int col[100100];
ll in[100100][3];

int main() {
	ll lim[3];
	ll cnt[3] = {};
	cin >> lim[0] >> lim[1] >> lim[2];
	const int N = lim[0] + lim[1] + lim[2];
	memset(col,-1,sizeof(col));

	priority_queue<pll> q[3][2];
	rep(i,N) {
		rep(j,3) cin >> in[i][j];
		ll mx = -2e9;
		int add = -1;
		int mv = -1;
		rep(j,3) {
			ll score = -2e9;
			int mv_ = -1;
			if(cnt[j] < lim[j]) {
				score = in[i][j];
			}
			else {
				rep(k,2) {
					if(cnt[(j+k+1)%3] >= lim[(j+k+1)%3]) {
						while(q[j][k].size() && col[q[j][k].top().se] != j) q[j][k].pop();
						assert(q[j][k].size());
						while(q[(j+k+1)%3][k].size() && col[q[(j+k+1)%3][k].top().se] != (j+k+1)%3) q[(j+k+1)%3][k].pop();
						assert(q[(j+k+1)%3][k].size());

						ll score_ = q[(j+k+1)%3][k].top().fi + q[j][k].top().fi + in[i][j];
						if(score < score_) {
							score = score_;
							mv_   = k;
						}
					}
					else {
						while(q[j][k].size() && col[q[j][k].top().se] != j) {
							q[j][k].pop();
						}
						assert(q[j][k].size());
						if(score < q[j][k].top().fi + in[i][j]) {
							score = q[j][k].top().fi + in[i][j];
							mv_ = k;
						}
					}
				}
			}
			if(mx < score) {
				mx  = score;
				add = j;
				mv = mv_;
			}
		}
		assert(add>=0);
//		cout << "hoge" << endl;

		if(cnt[add] >= lim[add]) {
			int idx = (add+mv+1)%3;
			pii t;
			// pre move
			if(cnt[idx] >= lim[idx]) {
				t = q[idx][mv].top();
				q[idx][mv].pop();
				rep(j,2) {
					q[(idx+1+mv)%3][j].push(pii(in[t.se][(idx+1+mv + j+1)%3] - in[t.se][(idx+1+mv)%3], t.se));
				}
				cnt[idx]--; cnt[(idx+1+mv)%3]++;
				col[t.se] = (idx+1+mv)%3;
			}

			// move to taregt
			t = q[add][mv].top();
			q[add][mv].pop();
			rep(j,2) {
				q[idx][j].push(pii(in[t.se][(idx+j+1)%3] - in[t.se][idx], t.se));
			}
			cnt[add]--; cnt[idx]++;
			col[t.se] = idx;
		}
		col[i] = add;
		cnt[add]++;
		rep(j,2) {
			q[add][j].push(pii(in[i][(add+j+1)%3] - in[i][add],i));
		}
		//cout << add << endl;
	}
//	rep(i,N) cout << col[i] << endl;

	ll res = 0;
	rep(i,N) {
		res += in[i][col[i]];
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 9448
// E - Bomber

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

set<pair<int, int>> hw;
unordered_map<int, int> cnt_h;
unordered_map<int, int> cnt_w;
unordered_set<int> max_h_set;
unordered_set<int> max_w_set;

int main() {
	int H, W, M;
	cin >> H >> W >> M;

	int max_cnt_h = 0;
	int max_cnt_w = 0;
	for (int i=0; i<M; i++) {
		int h, w;
		cin >> h >> w;

		hw.insert(make_pair(h, w));

		cnt_h[h]++;
		cnt_w[w]++;

		if (cnt_h[h] > max_cnt_h) {
			max_h_set.clear();
			max_h_set.insert(h);
			max_cnt_h = cnt_h[h];
		} else if (cnt_h[h] == max_cnt_h) {
			max_h_set.insert(h);
		}

		if (cnt_w[w] > max_cnt_w) {
			max_w_set.clear();
			max_w_set.insert(w);
			max_cnt_w = cnt_w[w];
		} else if (cnt_w[w] == max_cnt_w) {
			max_w_set.insert(w);
		}
	}

	bool no_common = false; // 交点に共通の爆破対象がないところが一つでもあればtrue
	for (int h : max_h_set) {
		for (int w : max_w_set) {
			if (hw.find(make_pair(h, w)) == hw.end()) {
				no_common = true;
				break; // M + 1 回目までに必ずbreakされる
			}
		}
	}

	// **** debug ****
	/*
	if (no_common) cout << "no common exists" << endl;
	else cout << "all common" << endl;
	*/

	int ans;
	if (no_common) ans = max_cnt_h + max_cnt_w;
	else ans = max_cnt_h + max_cnt_w - 1;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 71088
#include <bits/stdc++.h>
using namespace std;
int INF = 10000000;
int main(){
  while (1){
    int n, m, c, s, g;
    cin >> n >> m >> c >> s >> g;
    if (n == 0 && m == 0 && c == 0 && s == 0 && g == 0){
      break;
    }
    s--;
    g--;
    vector<vector<vector<int>>> E(c, vector<vector<int>>(n, vector<int>(n, INF)));
    for (int i = 0; i < m; i++){
      int x, y, d, c2;
      cin >> x >> y >> d >> c2;
      x--;
      y--;
      c2--;
      E[c2][x][y] = min(E[c2][x][y], d);
      E[c2][y][x] = min(E[c2][y][x], d);
    }
    vector<int> p(c);
    for (int i = 0; i < c; i++){
      cin >> p[i];
    }
    vector<vector<int>> E2(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++){
      E2[i][i] = 0;
    }
    for (int i = 0; i < c; i++){
      for (int j = 0; j < n; j++){
        E[i][j][j] = 0;
      }
      for (int j = 0; j < n; j++){
        for (int k = 0; k < n; k++){
          for (int l = 0; l < n; l++){
            E[i][k][l] = min(E[i][k][l], E[i][k][j] + E[i][j][l]);
          }
        }
      }
      vector<int> q(p[i] + 1);
      q[0] = 0;
      for (int j = 1; j < p[i]; j++){
        cin >> q[j];
      }
      q[p[i]] = 20000;
      vector<int> r(p[i]);
      for (int j = 0; j < p[i]; j++){
        cin >> r[j];
      }
      vector<int> cost(20000);
      cost[0] = 0;
      for (int j = 0; j < p[i]; j++){
        for (int k = q[j] + 1; k <= q[j + 1]; k++){
          cost[k] = cost[k - 1] + r[j];
        }
      }
      for (int j = 0; j < n; j++){
        for (int k = 0; k < n; k++){
          if (E[i][j][k] != INF){
            E2[j][k] = min(E2[j][k], cost[E[i][j][k]]);
          }
        }
      }
    }
    for (int i = 0; i < n; i++){
      for (int j = 0; j < n; j++){
        for (int k = 0; k < n; k++){
          E2[j][k] = min(E2[j][k], E2[j][i] + E2[i][k]);
        }
      }
    }
    if (E2[s][g] == INF){
      cout << -1 << endl;
    } else {
      cout << E2[s][g] << endl;
    }
  }
}


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

using namespace std;

#define ll long long

void move(char c, int& x, int& y) {
	const static string N = "ABCDEFGHIJKLM";
	const static string S = "NOPQRSTUVWXYZ";
	const static string E = "abcdefghijklm";
	const static string W = "nopqrstuvwxyz";
	for (int i = 0; i < N.size(); ++i) {
		if (c == N[i]) {
			++y; return;
		}
	}
	for (int i = 0; i < S.size(); ++i) {
		if (c == S[i]) {
			--y; return;
		}
	}
	for (int i = 0; i < E.size(); ++i) {
		if (c == E[i]) {
			++x; return;
		}
	}
	for (int i = 0; i < W.size(); ++i) {
		if (c == W[i]) {
			--x; return;
		}
	}
}

signed main() {
	int n; cin >> n;
	string s; cin >> s;

	int x, y; x = y = 0;
	for (int i = 0; i < n; ++i) {
		char si = s[i];
		move(si, x, y);
	}

	string new_code = "";
	if (x > 0) {
		while (x--)
			new_code += "a";
	}
	else if (x < 0) {
		x = -x;
		while (x--)
			new_code += "n";
	}
	if (y > 0) {
		while (y--)
			new_code += "A";
	}
	else if (y < 0) {
		y = -y;
		while (y--)
			new_code += "N";
	}

	cout << (new_code.size()) << endl;
	cout << new_code << endl;

	return 0;
}


Measured memory_bytes: 3340
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std ;
int main()
{
    ios_base::sync_with_stdio(false) ;
    cin.tie(0);
    cout.tie(0);
    ll n ;
    cin >> n ;
//    cin.ignore() ;
    string str ;
    cin >> str ;
    vector <int> w ;
    vector <int> r ;
    for(int i = 0 ; i < n ; i++)
    {
        if(str[i] == 'W') w.push_back(i) ;
        else r.push_back(i) ;
    }
    int wInd = 0 , rInd = r.size()-1 ;
    int cnt = 0;
    while( (wInd < w.size()) && (rInd >= 0) && (w[wInd] < r[rInd]) )
    {
        cnt++ ;
        wInd++ ;
        rInd -- ;
    }
    cout << cnt << endl ;
}


Measured memory_bytes: 4832
def main():
    S = input()

    for i, s in enumerate(S):
        if i % 2 == 0:
            if s == 'h':
                continue
            else:
                print('No')
                exit()
        else:
            if s == 'i':
                continue
            else:
                print('No')
                exit()
    if i % 2 == 0:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,h,w,i,a,b,ans=0;
	cin>>n>>h>>w;
	for (i=1;i<=n;i++) {
		cin>>a>>b;
		if (a>=h&&b>=w) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [ x for x in input().split(" ")]
orig_A = A[:]

#bubblesort
for i in range(0, N):
    for j in range(N-1, i, -1):
        if int(A[j][1]) < int(A[j-1][1]):
            A[j], A[j-1] = A[j-1], A[j]

print(*A)
print("Stable")


#selectionsort
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if int(orig_A[j][1]) < int(orig_A[minj][1]):
            minj = j
    orig_A[i], orig_A[minj] = orig_A[minj], orig_A[i]


print(*orig_A)
print("Stable" if A == orig_A else "Not stable")

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

int main(){
	int a, b;
	cin >> a;
	cin >> b;
	double a2 = a, b2 = b;
	cout << a / b << endl << a%b << endl;
	cout.setf(ios_base::fixed, ios_base::floatfield);
    cout << setprecision(10) << a2 / b2 << endl;
	return 0;
}

Measured memory_bytes: 3264
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(l.begin(),l.end(),greater<int>());
    int ans =0;
    for(int i=0; i<k; i++){
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

INF = float('inf')
DF = 300
last = [0] * 26
cur_ans = []
nexts = []
for i,s in enumerate(S):
    best_k = -1
    best_score = -INF
    scores = []
    for k,s in enumerate(s):
        score = s
        for j,c in enumerate(C):
            if j==k: continue
            score -= c * (i+1 - last[j])
        if score > best_score:
            best_score = score
            best_k = k
        scores.append((score,k))
    last[best_k] = i+1
    cur_ans.append(best_k + 1)
    for sc,k in scores:
        if k==best_k: continue
        if sc < best_score - DF: continue
        nexts.append((best_score-sc, i,k))
nexts.sort(key=lambda x:x[0])

def evaluate(ans):
    last = [0] * 26
    score = 0
    for i,(s,a) in enumerate(zip(S,ans)):
        score += s[a-1]
        last[a-1] = i+1
        for j,c in enumerate(C):
            score -= c * (i+1 - last[j])
    return score + 10**6

cur_score = evaluate(cur_ans)
selects = [-1] * D
for _,ni,nk in nexts:
    if selects[ni] >= 0: continue
    last = [0] * 26
    ans = []
    for i,s in enumerate(S):
        if selects[i] >= 0:
            last[selects[i]] = i+1
            ans.append(selects[i] + 1)
            continue
        if i==ni:
            last[nk] = i+1
            ans.append(nk + 1)
            continue
        best_k = -1
        best_score = -INF
        for k,s in enumerate(s):
            score = s
            for j,c in enumerate(C):
                if j==k: continue
                score -= c * (i+1 - last[j])
            if score > best_score:
                best_score = score
                best_k = k
        last[best_k] = i+1
        ans.append(best_k + 1)
    sc = evaluate(ans)
    if sc > cur_score:
        cur_score = sc
        cur_ans = ans
        selects[ni] = nk

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

Measured memory_bytes: 70312
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    int n, k; cin >> n >> k;
    set<int> s;
    rep(i, k) {
        int d; cin >> d;
        rep(j, d) {
            int a; cin >> a;
            s.insert(a);
        }
    }
    cout << n - s.size() << endl;
}


Measured memory_bytes: 3584
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define ll long long

void solve()
{
    ll X;
    cin >> X;
    while (1)
    {
        bool isPrime = true;
        for (int i = 2; i < sqrt(X); i++)
        {
            if (X % i == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            cout << X << endl;
            return;
        }
        X++;
    }

    return;
}

int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int q;
    cin >> q;
    while (q--)
    {
        string s;
        cin >> s;
        queue<int> que[100];
        int pos = 0, depth = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '[')
                depth++;
            else if (s[i] == ']')
            {
                vector<int> v;
                while (!que[depth].empty())
                {
                    int n = que[depth].front();
                    que[depth].pop();
                    v.push_back(n);
                }
                sort(all(v));
                int sum = 0;
                rep(i, (v.size() + 1) / 2) sum += v[i];
                que[depth - 1].push(sum);
                depth--;
                //cout << sum << endl;
            }
            else
            {
                int num = 0;
                while ('0' <= s[i] && s[i] <= '9')
                {
                    int n = s[i] - '0';
                    num = 10 * num + n;
                    i++;
                }
                i--;
                //cout << num << " " << depth << endl;
                que[depth].push((num + 1) / 2);
            }
        }
        cout << que[0].front() << endl;
        //return 0;
    }
}



Measured memory_bytes: 3340
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>

struct Store
{
	long long price, num;
};

long long n, m, ans;
Store a[100010];

bool cmp(const Store &a, const Store &b)
{
	return a.price < b.price;
}

int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0), std::cout.tie(0);
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i].price >> a[i].num;
	std::sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; ++i)
	{
		if (m >= a[i].num)
			ans += a[i].num * a[i].price, m -= a[i].num;
		else
		{
			ans += a[i].price * m;
			break;
		}
	}
	std::cout << ans << "\n";
	return 0;
}

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

public class Main{
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}
        String next(){while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());}catch (IOException  e){e.printStackTrace();}}return st.nextToken();}
        int nextInt(){return Integer.parseInt(next());}
        long nextLong(){return Long.parseLong(next());}
        double nextDouble(){return Double.parseDouble(next());}
        int[] readArray(int n){int[] a=new int[n];for (int i=0; i<n; i++) a[i]=nextInt();return a;}
        long[] readLongArray(int n){long[] a=new long[n];for (int i=0; i<n; i++) a[i]=nextLong();return a;}
        String nextLine(){String str = "";try{str = br.readLine();}catch (IOException e){e.printStackTrace();}return str;}
    }
    static int getgcd(int n1,int n2){
        while(n1 != n2){
            if(n1 > n2) n1 -= n2;
            else n2 -= n1;
        }
        return n1;
    }
    static boolean isSorted(int[] arr, int n){
        for(int i=1;i<n;i++){
            if(arr[i]<arr[i-1]) return false;
        }
        return true;
    }
    static boolean isPrime(long n){
        if(n==2) return true;
        else if(n%2==0) return false;
        for(int i=3;i<=n/2;i+=2){
            if(n%i==0) return false;
        }
        return true;
    }
    static void printArray(int[] arr){
        for(int x:arr){
            System.out.print(x+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        FastReader s=new FastReader();
        int x=s.nextInt();
        if(x>=400 && x<600) System.out.println("8");
        else if(x>=600 && x<800) System.out.println("7");
        else if(x>=800 && x<1000) System.out.println("6");
        else if(x>=1000 && x<1200) System.out.println("5");
        else if(x>=1200 && x<1400) System.out.println("4");
        else if(x>=1400 && x<1600) System.out.println("3");
        else if(x>=1600 && x<1800) System.out.println("2");
        else if(x>=1800 && x<2000) System.out.println("1");

    }
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<lint>> x(n, vector<lint>(3, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> x[i][j];
    }
  }
  lint ans = 0;
  for (int bit = 0; bit < 8; bit++) {
    vector<lint> v(n, 0);
    for (int i = 0; i < n; i++) {
      lint tmp = 0;
      for (int j = 0; j < 3; j++) {
        if (bit & (1 << j))
          tmp += x[i][j];
        else
          tmp -= x[i][j];
      }
      v[i] = tmp;
    }
    sort(begin(v), end(v), greater<lint>());
    lint res = 0;
    for (int i = 0; i < m; i++) {
      res += v[i];
    }
    // cout << res << " ";
    // for (auto &&w : v) {
    //   cout << w << " ";
    // }
    // cout << endl;
    ans = max(ans, res);
  }
  cout << ans << endl;
}

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

void Print(const vector<int>& xs) {
  for (const auto& x : xs) cout << x << ", ";
  cout << endl;
}

int main() {
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  
  unordered_set<int> x_set;
  for (int i = 0;; ++i) {
    if (100 * A * i > F) break;
    for (int j = 0;; ++j) {
      int x = 100 * A * i + 100 * B * j;
      if (x > F) break;
      x_set.insert(x);
    }
  }
  vector<int> x_vec(x_set.begin(), x_set.end());
  sort(x_vec.begin(), x_vec.end());
  
  unordered_set<int> y_set;
  for (int i = 0;; ++i) {
    if (C * i > F) break;
    for (int j = 0;; ++j) {
      int y = C * i + D * j;
      if (y > F) break;
      y_set.insert(y);
    }
  }
  vector<int> y_vec(y_set.begin(), y_set.end());
  sort(y_vec.begin(), y_vec.end());
  
  double density_max = -1, amout_max, sugar_max;
  for (const auto& a : x_vec) {
    for (const auto& b : y_vec) {
      if (a + b == 0) continue;
      if (a + b > F) continue;
      if ((double)b / a > E / 100.) continue;
      double density = 100. * b / (a + b);
      if (density > density_max) {
        density_max = density;
        amout_max = a + b;
        sugar_max = b;
      }
    }
  }
  cout << amout_max << " " << sugar_max << endl;
}


Measured memory_bytes: 512
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)
# print(C)
# combinations()
al = 0
for ball, num in C.items():
    al += num * (num - 1) // 2
# print(al)
for a in A:
    ball = a
    num = C[a]
    ans = al - C[a] * (C[a] - 1) // 2 + (C[a] - 1) * (C[a] - 2) // 2
    print(ans)

# for a in A:
#     c[a]

Measured memory_bytes: 27152
#include <bits/stdc++.h>
using namespace std;
int main(void){
    char tmp =' '; //スペース入れる
    map<char, char> dic{}; //(辞書)
    dic['A'] = 'T';
    dic['T'] = 'A';
    dic['G'] = 'C';
    dic['C'] = 'G';
    
    cin >> tmp;
    cout << dic[tmp];
}

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

int main(){
    int n; cin >> n;
    vector<int> d(n);
    rep(i,n) cin >> d[i];
    sort(d.begin(),d.end());
    cout << d[n/2]-d[n/2-1] << endl;
}

Measured memory_bytes: 640
n,k=map(int,input().split())
s=input()
b=[1]
if s[0]=="0":b=[0,1]
for i in range(1,n):
  if s[i-1]!=s[i]:b+=[1]
  else:b[-1]+=1
if s[-1]=="0":b+=[0]
if len(b)//2<=k:print(n);exit()
#print(b)

x=a=sum(b[:k*2+1])
#print(b[:k*2+1])
for i in range(k,len(b)//2):
  a+=b[i*2+1]+b[(i+1)*2]
  a-=b[(i-k)*2]+b[(i-k)*2+1]
  x=max(a,x)
  #print(b[(i-k)*2+2:(i+1)*2+1])
print(x)

Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define EPS 1e-9
#define mp make_pair
#define x first
#define y second
const double PI = acos(-1);

typedef pair<int, int> pii;

int n,a[200],x;


int main() {
	cin >> n >> x;
	for (int i = 0; i < n; ++i){
		cin >> a[i];
	}	
	sort(a,a+n);
	int cnt = 0;
	for (int i = 0; i < n; ++i){
		if(x >= a[i]){
			cnt++;
			x -= a[i];
		}
	}
	if(cnt == n && x )cnt--;
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  vector<int> over(0);
  int64_t sum = 0;
  
  for(int i=0; i<N; i++){
    cin >> A[i];
    cin >> B[i];
    sum += A[i];
    if(A[i] > B[i]){
      over.push_back(B[i]);
    }
  }
  
  sort(over.begin(),over.end());
  if(over.size() == 0){
    cout << 0 << endl;
  }
  else{
    cout << sum - over[0] << endl;
  }
}

Measured memory_bytes: 3832
#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

int main()
{
   int n, curr;
   int maxv = INT_MIN, minv = INT_MAX;
   cin >> n;
   cin >> curr;
   minv = curr;
   for (int i = 1; i < n; ++i)
   {
       cin >> curr;
       /** 在这要先求出当前的的最大值，如果先求最小值，递减序列会恒为０*/
       maxv = max(maxv, curr-minv);
       minv = min(minv, curr);
   }

   cout << maxv << endl;
}



Measured memory_bytes: 3092
N=int(input())
D=[list(map(int,input().split())) for i in range(N)]
tf=0
for j in range(N-2):#Di1=Di2&Di+1_1=Di+1_2&Di1=Di2 3回連続ぞろ目
    if D[j][0]==D[j][1] and D[j+1][0]==D[j+1][1] and D[j+2][0]==D[j+2][1]:
        tf=1
        break

if tf==1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9192
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    n = ii()
    s = input().rstrip()
    print(s) if n >= 3200 else print("red")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
n = int(input())
s = list(map(int, input().strip().split(' ')))
t = n // 2

for i in range(0, n // 2):
    s[i], s[n - i - 1] = s[n - i - 1], s[i]

for i in range(0, len(s)):
    if i != len(s) - 1:
        print(s[i], end=" ")
    else:
        print(s[i])


Measured memory_bytes: 5604
# ARC067D - Walk and Teleport (ABC052D)
def main():
    # choose A * dist[i, j] or B
    N, A, B = tuple(map(int, input().split()))
    X = tuple(map(int, input().split()))
    D = [j - i for i, j in zip(X, X[1:])]  # distance
    ans = sum(min(A * d, B) for d in D)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 15148
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

res = 0
for i in range(n):
    if a[i]>=b[i]:
        res += b[i]
    else:
        res += a[i]
        b[i]-=a[i]
        if a[i+1] >= b[i]:
            res += b[i]
            a[i+1] -= b[i]
        else:
            res += a[i+1]
            a[i+1] = 0
print(res)

Measured memory_bytes: 18476
def newdigit( keta, add, oldsum )
	if keta % 2 == 0 
		add2 = add * 2
		if add2 >= 10
			add2 = 1 + add2 % 10
		end
	else
		add2 = add
	end
	oldsum + add2
end

def checkdigit( adigit )
	sum = 0
	adigit.reverse.each_with_index{|e,i|
		add = e 
		if i % 2 == 1
			add = e * 2
			if add >= 0
				t = add / 10 + add % 10
				add = t
			end
		end
		sum += add
	}
#	puts "sum = #{sum}"
	if sum % 10 == 0 
		true
	else
		false
	end
end

def	setnums( endlevel,level, aryAst, numCandidate, aryCandidate,keta, digit)
#print "level = #{level} digit = #{digit} "
#p aryCheckNum

	if endlevel == level 
		if digit % 10 == 0
			$count += 1
		end
	else
		numCandidate.times{ |i|
			tempdigit = newdigit( keta-aryAst[level], aryCandidate[ i ],digit)
			setnums( endlevel, level + 1, aryAst, numCandidate,aryCandidate, keta, tempdigit)
		}
	end
end

def main
	n      = $stdin.gets.chomp.to_i
	strID  = $stdin.gets.chomp
	m      = $stdin.gets.chomp.to_i
	aryCandidate = $stdin.gets.chomp.split(/ /).map{|n| n.to_i}

	aryAst = Array.new
	aryCheckNum = Array.new

	digit = 0
	strID.split(//).each_with_index{ |e,i|
		if e == '*'
			aryAst << i
			aryCheckNum << '*'
		else
			aryCheckNum << e.to_i
			digit = newdigit( n-i, e.to_i, digit)
		end
	}

#start_time = Time.now
	$count = 0 
	setnums( aryAst.size, 0, aryAst, aryCandidate.size, aryCandidate, n, digit )
	p $count
#p "#{Time.now - start_time}s"
end
main


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

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


int main(){
    
    int n,x;
    int a[100];
    cin >> n >> x;
    rep(i,n) cin >> a[i];

    sort(a,a+n);

    int cnt = 0;
    for(int i = 0;i<n;i++){
        if(x >= a[i]){
            cnt++;
           if(i==n-1){
            if(x>a[i]) cnt--;
            }
            x -= a[i];
        }
    }
    
    cout << cnt << endl;

    return 0;
};



Measured memory_bytes: 256
#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<cmath>
    #include<climits>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<bitset>
    #include<iomanip>
    using namespace std;
     
    #define rep(i,j,n) for(int i=(j);i<(n);i++)
    #define rep2(i,j,n) for(int i=(j);i<=(n);i++)
    #define all(i) i.begin(),i.end()
     
    typedef vector<int> vi;
    typedef vector<vector<int>> vvi;
    typedef vector<string> vs;
    typedef vector<vector<string>> vvs;
    typedef pair<int, int> pi;
    typedef long long i64;
     
    int main() {
    	int n, m;
    	cin >> n;
    	map<string, int> blue;
    	set<string> word;
    	rep(i, 0, n) {
    		string s;
    		cin >> s;
    		word.insert(s);
    		if (!blue.count(s)) {
    			blue[s] = 0;
    		}
    		blue[s]++;
    	}
    	cin >> m;
    	map<string, int> red;
    	rep(i, 0, m) {
    		string s;
    		cin >> s;
    		if (!red.count(s)) {
    			red[s] = 0;
    		}
    		red[s]++;
    	}
    	int ans = 0;
    	for (auto ite : word) {
    		if (red.count(ite)) {
    			ans = max(ans, blue[ite] - red[ite]);
    		}
    		else {
    			ans = max(ans, blue[ite]);
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

int N, K;

void solve()
{
    cin >> N >> K;
    int ans = 1;

    REP(i, N)
    {
        ans = min(ans * 2, ans + K);
    }

    cout << ans << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    solve();

    return 0;
}

Measured memory_bytes: 256
//AOJ 0558
#include <iostream>
#include <queue>
#include <fstream>
using namespace std;

int h, w, n;
char map[1024][1024];
//到当前工厂距&#31163;
int d[1024][1024];
int direction[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
int factory[16][2];
typedef pair<int, int>point;

int bfs(int sx, int sy, int gx, int gy){
	for (int i = 0; i < h; ++i)
		for (int j = 0; j < w; ++j)
			d[i][j] = -1;
	queue<point>q;
	q.push(point(sx, sy));
	d[sx][sy] = 0;
	while (!q.empty()){
		point cur = q.front();
		q.pop();
		if (cur == point(gx, gy))
			break;
		for (int i = 0; i < 4; ++i){
			int nx = cur.first + direction[i][0];
			int ny = cur.second + direction[i][1];
			if (nx >= 0 && ny >= 0 && nx < h&&ny < w
				&&map[nx][ny]!='X'&&d[nx][ny]==-1){
				q.push(point(nx, ny));
				d[nx][ny] = d[cur.first][cur.second] + 1;
			}
		}
	}
	return d[gx][gy];
}
int main(){
	//ifstream in("E:\\in.txt");
	while (cin >> h >> w >> n){
		if (!h || !w || !n)
			return 0;
		for (int i = 0; i < h; ++i){
			for (int j = 0; j < w; ++j){
				cin >> map[i][j];
				if (map[i][j] == 'S'){
					factory[0][0] = i;
					factory[0][1] = j;
					map[i][j] = '.';
				}
				else if (isdigit(map[i][j])){
					int index = map[i][j] - '0';
					factory[index][0] = i;
					factory[index][1] = j;
				}
			}
		}
		int step = 0;
		for (int i = 0; i < n; ++i){
			step += bfs(factory[i][0], factory[i][1], 
				factory[i + 1][0], factory[i + 1][1]);
		}
		cout << step << "\n";
	}
	return 0;
}

Measured memory_bytes: 6304
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()

Measured memory_bytes: 25208