akhauriyash/Code-Regression huggingface dataset:
_,a=open(0)
a=[0]+list(map(int,a.split()))+[0]
A=abs
c=sum(A(j-i)for i,j in zip(a,a[1:]))
for i,j,k in zip(a,a[1:],a[2:]):print(c-A(j-i)-A(k-j)+A(k-i))

Measured memory_bytes: 13800
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define vct vector<ll>
#define umap map<ll,ll>

int main()
{
    ll a,c,b;
    cin>>a>>b>>c;
    c-=(a-b);
    cout<<max(1LL*0,c);
    
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
ans = 0 ;count = 0 ;pro = 1

x=int(input())
for i in range(1,10**9):
    count+=i
    if x<=count:
        print(i)
        exit()


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

int f(int64_t a, int64_t b) {
  int keta = 0;
  if (a > b) {
    while (a) {
      a /= 10;
      keta++;
    }
    return keta;
  }else {
    while (b) {
      b /= 10;
      keta++;
    }
    return keta;
  }
}

int main() {
  int64_t n; cin >> n;
  int answer = 1000000000;
  for (int64_t a = 1; a <= sqrt(n); a++) {
    if (n % a == 0) {
      answer = min(answer, f(a, n / a));
    }
  }
  cout << answer;
}

Measured memory_bytes: 3680
#include <iostream>

using namespace std;


int totalDate(int month, int date)
{
	static const int MONTH[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

	int sum = 0;
	for(int i = 0; i < month-1; i++)
		sum += MONTH[i];

	return sum + date;
}

const char* day(int total_date)
{
	static const char* DAY[] = {"Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday"};

	return DAY[(total_date-1)%7];
}

int main()
{
	while(true)
	{
		int month, date;
		cin >> month >> date;

		if(month == 0)
			break;

		cout << day(totalDate(month, date)) << endl;
	}

	return 0;
}

Measured memory_bytes: 1156
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))

def ink(L):
    cnt = 0
    for i in range(N):
        cnt += A[i]//L
        if A[i]%L != 0:
            cnt += 1
        cnt -= 1
    return cnt <= K

bottom, top = 0, max(A)

while(top - bottom > 1):
    middle = (top + bottom) // 2
    if ink(middle): top = middle
    else: bottom = middle

print(top)

Measured memory_bytes: 104120
A=int(input())
B=int(input())
C=int(input())
X=int(input())

def f(a,b,c,x):
  count = 0
  for i in range(a+1):
    for j in range(b+1):
      for k in range(c+1):
        if 500*i + 100*j + 50*k == x:
          count += 1
  print(count)

f(A,B,C,X)

Measured memory_bytes: 3060
A11, A12, A13 = map(int, input().split())
A21, A22, A23 = map(int, input().split())
A31, A32, A33 = map(int, input().split())
N = int(input())
B = [int(input()) for _ in range(N)]

flag = False
if A11 in B and A12 in B and A13 in B:
    flag = True
elif A21 in B and A22 in B and A23 in B:
    flag = True
elif A31 in B and A32 in B and A33 in B:
    flag = True
elif A11 in B and A21 in B and A31 in B:
    flag = True
elif A12 in B and A22 in B and A32 in B:
    flag = True
elif A13 in B and A23 in B and A33 in B:
    flag = True
elif A11 in B and A22 in B and A33 in B:
    flag = True
elif A13 in B and A22 in B and A31 in B:
    flag = True

if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    int n;
    cin >> n;
    if(n<=999) cout << "ABC" << endl;
    else cout <<"ABD" << endl;
}

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

using namespace std;
using ll = long long;

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

    vector<ll> tab(n+10);

    for (int i = 0; i <= n+1; ++i) {
        tab.at(i) = 0;
    }

    for (ll i = 0; i < m; ++i) {
        ll tl, tr;
        cin >> tl >> tr;
        tab.at(tl) += 1;
        tab.at(tr+1) -= 1;
    }

    for (int i = 0; i <= n; ++i) {
        if (0 < i) tab.at(i) += tab.at(i-1);
    }

    ll cnt = 0;
    for (int i = 0; i <= n; ++i) {
        if(tab.at(i) == m) cnt++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 1024
def abc104():

	p,c=[],[]
	D,G=map(int,input().split())
	for i in range(D):
		P,C=map(int,input().split())
		p.append(P)
		c.append(C)


	def saisho(a,b):
		if a==0:
			return 10**10
		m=min(b//(a*100),p[a-1])
		s=100*a*m
		if m==p[a-1]:
			s+=c[a-1]
		if s<b:
			m+=saisho(a-1,b-s)
		return min(m,saisho(a-1,b))
	
	print(saisho(D,G))
	
abc104()

Measured memory_bytes: 41584
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int n,i,ans=0;
    cin >> n;
    vector<int> v(n),c(n);
    for(i=0;i<n;i++) cin >> v[i];
    for(i=0;i<n;i++) cin >> c[i];
    for(i=0;i<n;i++) ans += max(0,v[i]-c[i]);
    cout << ans;
}

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

using namespace std;

int main(void) {
    vector<int> vec(3);
    cin >> vec[0] >> vec[1] >> vec[2];
    sort(vec.rbegin(), vec.rend());
    cout << vec[0]*10+vec[1] + vec[2] << endl;
    return 0;
}


Measured memory_bytes: 256
[N,A,B] = list(map(int,input().split()))
AA = A-1
BB = N-B
sa = B - A
if sa%2==0:  #偶数
    out=sa//2

else:  #奇数
    if AA<BB:
        out = AA + 1 + (sa-1)//2
    else:
        out = BB + 1 + (sa-1)//2

print(out)


Measured memory_bytes: 39860
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

long[] AS, BS;

void main()
{
    auto N = readln.chomp.to!long;
    AS = readln.split.to!(long[]);
    BS = readln.split.to!(long[]);

    long[][3] DP;
    foreach (ref dp; DP) dp.length = N+1;
    foreach_reverse (j; 0..N+1) {
        foreach_reverse (i; 0..3) {
            long r1, r2;
            r1 = i == 2 ? N-j : DP[i+1][j];
            if (j+AS[i] <= N) {
                r2 = DP[i][j+AS[i]] + BS[i];
            }
            DP[i][j] = max(r1, r2);
        }
    }
    auto M = DP[0][0];
    foreach (ref dp; DP) {
        dp[] = 0;
        dp.length = M+1;
    }
    foreach_reverse (j; 0..M+1) {
        foreach_reverse (i; 0..3) {
            long r1, r2;
            r1 = i == 2 ? M-j : DP[i+1][j];
            if (j+BS[i] <= M) {
                r2 = DP[i][j+BS[i]] + AS[i];
            }
            DP[i][j] = max(r1, r2);
        }
    }

    writeln(DP[0][0]);
}

Measured memory_bytes: 591228
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
#define rsort(n) sort((n).begin(),(n).end(),greater<ll>())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 117117117117117

int main()
{
    ll n;
    vector<ll> num(5);
    cin >> n >> num[0] >> num[1] >> num[2] >> num[3]>>num[4];
    ll min;
    ssort(num);
    min=num[0];
    ll times=n/min;
    if(n%min!=0){
        times++;
    }
    cout << times+4 << endl;
}

Measured memory_bytes: 3592
N, K = map(int, input().split())
arr = [int(x) for x in input().split()]
ps = []
ms = []
for i in range(N):
    if arr[i] == 0:
        K -= 1
    elif arr[i] < 0:
        ms.append(abs(arr[i]))
    elif arr[i] > 0:
        ps.append(arr[i])
ms = ms[::-1]
if K <= 0:
    ans = 0
else:
    ans = ps[K-1] if K <= len(ps) else 10**18
    ans = min(ans, ms[K-1]) if K <= len(ms) else ans
if len(ps) > 0 and len(ms) > 0:
    for i in range(len(ms)):
        if K-(i+1)-1 < len(ps):
            ans = min(ans, ms[i]*2 + ps[K-(i+1)-1])
    for i in range(len(ps)):
        if K-(i+1)-1 < len(ms):
            ans = min(ans, ps[i]*2 + ms[K-(i+1)-1])
print(ans)


Measured memory_bytes: 14484
//In the name of 'ALLAH'
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

    ll n , k ;
    cin >> n >> k ;
    ll ans = k ;

    for(int i=1; i<n; i++)
    {
        ans *= (k-1);
    }
    cout << ans << endl;
}



Measured memory_bytes: 3504
#include<iostream>
using namespace std;
using ll = long long;
int main(){
    ll n,m,ans=-10000000000;
    cin >> n;
    for(ll i=0;i<n;i++){
        ll x;
        cin >> x;
        if(i==0)    m=x;
        else{
            if(ans<(x-m))   ans = x-m;
            if(m>x)     m=x;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3116
using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define rep(i,n) for (int i=0; i<n;++i)
int N,A,B;
int P[101];


int main() {
  cin >> N >> A >> B;
  rep(i, N) cin >> P[i];
  sort(P, P+N);
  int k1 = lower_bound(P, P+N, A+1)-P;
  int k2 = lower_bound(P, P+N, B+1)-P;
  cout << min(min(k1, k2-k1),N-k2) << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  string s[n];
  for(int i=0; i<n; i++) cin >> s[i];
  sort(s, s+n);
  int ans=1;
  for(int i=1; i<n; i++) {
    if(s[i]!=s[i-1]) ans++;
  }
  cout << ans;
}

Measured memory_bytes: 9888
//#pragma comment(linker,"/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
#define eps 1e-8
#define LL_INF 0x3fffffffffffffff
#define INF 0x3f3f3f3f
#define mem(a, b) memset(a, b, sizeof(a))
#define pper(i, n, m) for (int i = n; i >= m; i--)
#define repp(i, n, m) for (int i = n; i <= m; i++)
#define rep(i, n, m) for (int i = n; i < m; i++)
#define sa(n) scanf("%d", &(n))
#define slla(n) scanf("%lld", &(n))
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define DE(val) cout << #val << ": " << val << endl;
#define CASET             \
    int ___T, case_n = 1; \
    scanf("%d ", &___T);  \
    repp(i, 1, ___T)
 
const int dx44[6] = {0, -1, -1, 1, 1};
const int dy44[6] = {0, -1, 1, -1, 1};
const int dx4[6] = {0, 1, 0,-1};
const int dy4[6] = {-1, 0, 1,0};
const int dx8[9] = {0, -1, 0, 1, 0, 1, 1, -1, -1};
const int dy8[9] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
const int dx82[9] = {0, -1, -1, 1, 1, 2, 2, -2, -2};
const int dy82[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
ll po(ll a, ll b, ll mod)
{
    ll res = 1;
    a %= mod;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
ll gcd(ll a, ll b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        return gcd(b % a, a);
    }
}
void extgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if (!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        extgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
ll inverse(ll a, ll n)
{
    ll d, x, y;
    extgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const int maxn = 1e6 + 5;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
/*************************************************************************/

ll n,k;
ll v[maxn];
void solve() {
    slla(n);
    slla(k);
    repp(i,1,n) {
        slla(v[i]);
    }
    ll res = 0;
    repp(i,1,n) {
        ll cnt = 0;
        repp(j,i+1,n) {
            if(v[j] < v[i]) {
                cnt++;
            }
        }
        res += k*cnt % mod;
        res %= mod;

        cnt = 0;
        repp(j,1,n){
            if(v[j] < v[i]) {
                cnt++;
            }
        }
        res += k*(k-1)%mod*po(2,mod-2,mod)%mod*cnt%mod;
        res %= mod;
    }
    printf("%lld\n", res);
}

int main()
{

  
    
    // int t;
    // sa(t);
    // while(t--)
    solve();
    // int *x = new int[5]();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string ans;
	string s;

	cin >> s;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'B' && !ans.empty()) {
			ans.pop_back();
		}
		else if (s[i] == 'B' && ans.empty())
		{
			continue;
		}
		else
		{
			ans.push_back(s[i]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
ans = 0
for i in range(n):
    left = min(A[i], B[i])
    B[i] -= left
    ans += left
    right = min(A[i + 1], B[i])
    A[i + 1] -= right
    ans += right
 
print(ans)

Measured memory_bytes: 19116
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define all(container) container.begin(),container.end()
#define fast ios::sync_with_stdio(0); cin.tie(0)
const int mod = 1e9+7;  
int power(int a,int b) { if(b==0) return 1; int res = power(a,b/2); if(b&1) return res * res * a; else return res * res; }

template<class T> int size(T &&x) {
  return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
  return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
  out << '{';
  for(auto it = x.begin(); it != x.end(); ++it)
    out << *it << (it == prev(x.end()) ? "" : ", ");
  return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
  cerr << x << ";  ";
  dump(args...);
}
struct Nl{~Nl(){cerr << '\n';}};
# define print(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""

#define int long long

int32_t main(){
    
  fast;
  int x,y; cin >> x >> y;

  int price[206] = {0};
  price[1] = 300000;
  price[2] = 200000;
  price[3] = 100000;

  int ans = price[x] + price[y];
  
  if(x==1&&y==1) ans+=400000;

  cout << ans << '\n';
  

  return 0;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, '%d', $n);
fscanf(STDIN, '%s', $s);
fscanf(STDIN, '%d', $k);

$result = '';
$target = substr($s, $k - 1, 1);
for ($i = 0; $i < $n; $i++) {
    $result .= ($s[$i] === $target) ? $s[$i] : '*';
}

echo $result;


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

using namespace std;
#define ll long long
#define ld long double
#define point complex <ld>
#define x real()
#define y imag()
#define dot(a,b) ( (conj(a)*(b)).real() )
#define cross(a,b) ( (conj(a)*(b)).imag() )
#define vec(a,b) ((b)-(a))
#define eps 1e-8

int dcmp(ld a , ld b) {return fabs(a-b)<=eps ? 0: a<b ? -1 : 1;}

ld calc(point p , point p2)
{
    ld ds =  (p.x-p2.x)*(p.x-p2.x) + (p.y-p2.y)*(p.y-p2.y);
    return sqrt(ds);
}

bool check(point p , point p2 ,point p3)
{
    ld pp2 = calc(p,p2) , p2p3=calc(p2,p3);

    if (dcmp(pp2,p2p3) != 0) return 0;

    ld pp3 = calc(p,p3);

    if (dcmp(pp3 , sqrt(2)*pp2) != 0) return 0;
    point aa = vec(p,p2) , bb = vec(p,p3);
    if (cross(aa,bb) > 0) return 1;

    return 0;

}

bool isSq(point p , point p2 , point p3 , point p4)
{
    vector<point> v;
    v.push_back(p) , v.push_back(p2) , v.push_back(p3) , v.push_back(p4);

    map <ll,ll> mp;
    set <ll> st;
    for (int i=0; i<v.size(); i++)
    {
        for (int j=0; j<v.size(); j++)
        {
            if (i!=j)
            {
                mp[ (v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y) ]++;
                st.insert((v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y));
            }
        }
        if (mp.size()!=2) return 0;
        mp.clear();
    }
    if (st.size()!=2) return 0;
    set<ll> ::iterator it=st.begin();
    ll tmp=*it;
    it++; ll tmp2=*it;
    if (tmp2 != 2*tmp) return 0;

  //  point pp = vec(p,p2) , pp2 = vec(p,p3);
  //  if (cross(pp,pp2) > 0) return 1;
    return 1;
}

void solve(point p , point p2 , point p3)
{
    for(int i=-400; i<=400; i++)
    {
        for(int j=-400; j<=400; j++)
        {
            point p4(i,j);
            if (isSq(p,p2,p3,p4))
            {
                cout << p3.x << ' ' << p3.y << ' ' << p4.x << " " << p4.y << "\n";
                exit(0);
            }
        }
    }
}

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

    ll xx,yy,x2,y2,x3,y3,x4,y4;
    cin >> xx >> yy >> x2 >> y2;

    point p(xx,yy),p2(x2,y2);

    for(int i=-400; i<=400; i++)
    {
        for(int j=-400; j<=400; j++)
        {
            point p3(i,j);
            if (check(p,p2,p3))
            {
                solve(p,p2,p3);
            }
        }
    }
//
    return 0;
}

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

int main() {
  string s;
  cin >> s;
  map<char, int> m;
  for (int i = 0; i < s.size(); i++) {
    m[s[i]]++;
  }

  if (m.size() != 2) {
    cout << "No" << endl;
    return 0;
  }

  for (auto v : m) {
    if (v.second != 2) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

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

int main(){
  
  int n;
  cin>>n;
  int h[n];
  for(int i=0;i<n;i++) cin>>h[i];
  
  int a=100,count=0,ans=0,zero=0;
  while(true){
    a=100;
    zero=0;
    count=0;
    for(int i=0;i<n;i++){
      count++;
      if(h[i]==0){
        zero++; 
        count=0;
      }
      else if(h[i]!=0){ a=min(a,h[i]);}
      if(i!=n-1&&h[i]!=0&&h[i+1]==0){
        ans+=a;
        for(int j=i-count+1;j<i+1;j++){
          if(h[j]!=0){ h[j]-=a;}
        }
        count=0;
        a=100;
      }
      else if(i==n-1&&h[i]!=0){
        ans+=a;
        for(int j=i-count+1;j<i+1;j++){
          if(h[j]!=0){ h[j]-=a;}
        }
        count=0;
        a=100;
      }
    }
    
    if(zero==n) break;
  }
  
  cout<<ans<<endl;
  
}

Measured memory_bytes: 256
n,x = map(int,input().split())
l = list(map(int,input().split()))
d = [0]*(n+1)
count = 1
for i in range(1,n+1):
  d[i] = d[i-1]+l[i-1]
  if d[i]<=x: count += 1
print(count)


Measured memory_bytes: 2940
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
import heapq

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, L = MAP()
pq = [LIST() for _ in range(K)]
rs = [LIST() for _ in range(L)]

class UnionFind:
   def __init__(self, n):
       self.par = [i for i in range(n+1)]
       self.rank = [0] * (n+1)
   # 検索
   def find(self, x):
       if self.par[x] == x:
           return x
       else:
           self.par[x] = self.find(self.par[x])
           return self.par[x]
   # 併合
   def union(self, x, y):
       x = self.find(x)
       y = self.find(y)
       if self.rank[x] < self.rank[y]:
           self.par[x] = y
       else:
           self.par[y] = x
           if self.rank[x] == self.rank[y]:
               self.rank[x] += 1
   # 同じ集合に属するか判定
   def same_check(self, x, y):
       return self.find(x) == self.find(y)

tree_road = UnionFind(N)
tree_train = UnionFind(N)
for p, q in pq:
	tree_road.union(p, q)

for r, s in rs:
	tree_train.union(r, s)

dic = defaultdict(int)
for i in range(1, N+1):
	dic[(tree_road.find(i), tree_train.find(i))] += 1

for i in range(1, N+1):
	print(dic[(tree_road.find(i), tree_train.find(i))], end=" ")


Measured memory_bytes: 102664
S = gets.chomp
a = ['SUN','MON','TUE','WED','THU','FRI','SAT']
c = a.index(S)
case c
when 0 then
  puts 7
when 1 then
  puts 6
when 2 then
  puts 5
when 3 then
  puts 4
when 4 then
  puts 3
when 5 then
  puts 2
else
  puts 1
end

Measured memory_bytes: 1788
def main(n,k,q,x):
    ret=float('inf')
    for xi in x:
        c=[]
        tmp=[]
        for y in x:
            if y<xi:
                if len(tmp)>=k:
                    tmp.sort()
                    for j in range(len(tmp)-k+1):
                        c.append(tmp[j])
                tmp=[]
            else:
                tmp.append(y)
        if len(tmp)>=k:
            tmp.sort()
            for j in range(len(tmp)-k+1):
                c.append(tmp[j])
        if len(c)>=q:
            c.sort()
            ret=min(ret,c[q-1]-xi)
    return ret

#n=int(input())
#a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
n,k,q=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,k,q,x))


Measured memory_bytes: 70004
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] l = new int[n + 1];
        Arrays.setAll(l, i -> i == 0 ? 0 : scanner.nextInt());
        Arrays.sort(l);
        Arrays.parallelPrefix(l, Integer::sum);
        System.out.println(l[n] - l[n - k]);
    }
}

Measured memory_bytes: 28864
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))

ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll IMF = 1LL<< 29;
const double PI = 3.14159265358979323846;

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

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

        int ans = 0;
        for(int i = 0; i < n; i++){
                int sum = 0;
                for(int j = 0; j <= i; j++){
                        sum += a[j];
                }
                for(int j = i; j < n; j++){
                        sum += b[j];
                }

                chmax(ans, sum);
        }

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




Measured memory_bytes: 256
from collections import*
n,*a=map(int,open(0).read().split())


amaricard=n-sum([v-1 for k,v in Counter(a).items() if v>1 and (v-3)%2==0])
amari=[v-1 for k,v in Counter(a).items() if v>1 and (v-3)%2!=0]

if len(amari)==0:
    print(amaricard)
else:
    print(amaricard-sum(amari)-len(amari)%2)

Measured memory_bytes: 20004
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<string>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

struct UnionFind {
public:
    vector<int> d;
    UnionFind( int n ): d(n, -1) {}

    int find ( int x ) {
        if ( d[x] < 0 ) return x;
        return d[x] = find(d[x]);
    }

    bool unite( int x, int y ) {
        x = find(x);
        y = find(y);
        if ( x == y ) return false;
        if ( d[x] > d[y] ) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }

    bool same( int x, int y) {
        return find(x) == find(y);
    }

    int size ( int x ) {
        return -d[find(x)];
    }
};

int deg[100005];
vector<int> to[100005];

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    UnionFind uf(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        deg[a]++;
        deg[b]++;
        uf.unite(a,b);
    }
    rep(i, k) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    rep(i, n) {
        int ans = uf.size(i) - 1 - deg[i];
        for ( int u : to[i] ) {
            if ( uf.same(i,u)) --ans;
        }
        printf("%d%c", ans, i==n-1 ? '\n':' ');
    }

    return 0;
}

Measured memory_bytes: 6784
n,r,p,m;R(c){scanf("%d",&c);--r&&R();m=n-n/c/2*2*c;p+=p<n-m?(p/c%2?0:n/2)+p/c/2*c+p%c-p:p<n-m/2?m/2:n/2-n;}main(){for(;~scanf("%d%d",&n,&r);printf("%d\n",p))R(p=n-1);}

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  vector<int> d(10);
  d.at(0) = c * a - b;
  for(int i = 1; i < 10; i++){
    d.at(i) = d.at(i - 1) * a - b;
  }
  for(int x : d){
    cout << x << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI acos(-1.0)
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n,m;cin>>n>>m;
  int a[50],b[50],c[50],d[50];
  REP(i,n){
    cin>>a[i]>>b[i];
  }
  REP(i,m){
    cin>>c[i]>>d[i];
  }
  REP(i,n){
    int mn=INF;
    int index;
    REP(j,m){
      if(mn>abs(a[i]-c[j])+abs(b[i]-d[j])){
        index=j+1;
        mn=abs(a[i]-c[j])+abs(b[i]-d[j]);
      }
    }
    P(index);
  }
  return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextInt();
  int D = nextInt();
  int X = nextInt();
  int ans = X;
  REP(i, N) {
    int A = nextInt();
    ans += (D+A-1) / A;
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < n; i++)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    string S;
    cin >> S;

    int K;
    cin >> K;

    char tmp = S[K-1];
    string ans = "";
    rep (i, N) {
        if (S[i] == tmp) {
            ans += tmp;
        } else {
            ans += '*';
        }
    }

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

Measured memory_bytes: 256
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <deque>     // deque
#include <iomanip>   //setprecsion
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <utility>   // pair, make_pair
#include <vector>    // vector

#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>  //sin, cos, tan

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

void Main()
{
  vll a(3);
  rep (i, 3) cin >> a[i];
  ll k;
  cin >> k;
  sort(all(a));
  for(ll i = 0;i < k;i++)
  {
    a[2] *= 2;
  }
  fin(a[0] + a[1] + a[2]);
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  //cout << setfill('0') << internal << setw(4); 0埋め４桁
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i = 0; i < N; i++) {
    cin >> d.at(i);
  }

  int count = 0;
  vector<int> flag(101, 0);
  for(int i = 0; i < N; i++) {
    flag.at(d.at(i)) = 1;
  }
  for(int i = 0; i < 101; i++) {
    if(flag.at(i) == 1) {
      count++;
    }
  }
  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 3616
#include<stdio.h>
int parent(int);
int left(int);
int right(int);

main(){
  int heap[251],i,s,l,r;
  scanf("%d",&s);
  for(i=1; i <= s ; i++)
    scanf("%d",&heap[i]);
  for(i=1; i <= s ; i++){
    printf("node %d: key = %d, ",i,heap[i]);
    if(i >=2)
      printf("parent key = %d, ",heap[parent(i)]);
    l=left(i);
    r=right(i);
    if(l <= s)
      printf("left key = %d, ",heap[l]);
    if(r <= s)
      printf("right key = %d, ",heap[r]);
    printf("\n");
  }
  return 0;
}

int parent(int i){
  int x= i/2;
  return x;
}

int left(int i){
  int x = 2*i;
  return x;
}

int right(int i){
  int x = (2*i)+1;
  return x;
}

Measured memory_bytes: 600
import sys

n, *a = map(int, sys.stdin.read().split())

def main():
    c1 = c2 = s1 = s2 = 0
    for i in range(n):
        s1 += a[i]
        s2 += a[i]
        if i & 1:
            if s1 >= 0:
                c1 += s1 + 1
                s1 = -1
            if s2 <= 0:
                c2 += 1 - s2
                s2 = 1
        else:
            if s1 <= 0:
                c1 += 1 - s1
                s1 = 1
            if s2 >= 0:
                c2 += s2 + 1
                s2 = -1
    print(min(c1, c2))

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 14084
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static void Main() {
    var t = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    if (t[0] < 6) {
      Console.WriteLine(0);
    } else if (t[0] >= 6 && t[0] < 13) {
      Console.WriteLine(t[1] / 2);
    } else {
      Console.WriteLine(t[1]);
    }
  }
}

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

vector<pair<int64_t, int64_t>> p_fac(int64_t n)
{
    vector<pair<int64_t, int64_t>> res;
    for (int64_t p = 2; p * p <= n; p++)
    {
        if (n % p == 0)
        {
            int64_t e = 0;
            while (n % p == 0)
            {
                n /= p;
                e += 1;
            }
            res.push_back(make_pair(p, e));
        }
    }
    if (n != 1)
    {
        res.push_back(make_pair(n, 1));
    }
    return res;
}

void solve(int64_t N)
{
    auto f = p_fac(N);
    int64_t res = 0;
    for (auto pe : f)
    {
        int64_t e = pe.second;
        int64_t x = 1;
        while (true)
        {
            if (e < x)
                break;
            res++;
            e -= x;
            x++;
        }
    }
    cout << res << endl;
}

int main()
{
    int64_t N;
    cin >> N;
    solve(N);
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i , (n); ++i)
using ll = long long;
using namespace std;
int sum(int n) {
    if (n == 0) {
        return 0;
    }

    int s = sum(n - 1);
    return s + n;
}
int main() {
    int N,count=0;
    cin >> N;
    vector<int>A(N+5);
    for (int i = 0;i < N+1;i++) {
        cin >> A.at(i+1);
    }
    for (int i = 1;i < N+1;i++) {
        for (int j = 1;j < N+1;j++) {
            for (int k = 1;k < N+1;k++) {
                if (A.at(i) == A.at(j) || A.at(j) == A.at(k) || A.at(k) == A.at(i)) {
                    continue;
                }
                if (i<j&&j<k&&A.at(i) + A.at(j) > A.at(k) && A.at(j) + A.at(k) > A.at(i) && A.at(k) + A.at(i) > A.at(j)) {
                    count++;
                    //cout<<i<<' '<<j<<' '<<k<<endl;
                }
            }
        }
    }
    cout << count;
}


Measured memory_bytes: 3628
n,m = map(int,raw_input().split())
matrix = [[0 for x in xrange(m)] for y in xrange(n)]
vector = [0 for x in xrange(m)]
for x in xrange(n):
    matrix[x] = map(int,raw_input().split())
for x in xrange(m):
    vector[x] = input()
for x in xrange(n):
    ans = 0
    for y in xrange(m):
        ans += matrix[x][y]*vector[y]
    print ans

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

int main(){
	
	int n;
	
	while(cin>>n){
		if(n!=0){
			vector < vector<int> >m(n,vector<int>(n));
			int x=(n+1)/2;
			int y=n/2;
			m[x][y]=1;
			int j=2;
				while(j<=n*n){
						x++;
						y++;
					if(x>n-1)
					x=0;
					if(y<0)
					y=n-1;
					if(y>n-1)
					y=0;
					while(m[x][y]!=0){
						x++;
						y--;
					if(x>n-1)
					x=0;
					if(y<0)
					y=n-1;
					if(y>n-1)
					y=0;
				}
					m[x][y]=j++;
					
		}
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++)
				printf("%4d",m[i][j]);
				cout<<endl;
			}
	}
		else
			break;
	}
	
}

Measured memory_bytes: 1248
S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX

mod = int(1e9 + 7)

A_F_cnt = 0
B_F_cnt = 0

result = 1
sA = [ False for _ in range(MAX+1) ]
sB = [ False for _ in range(MAX+1) ]

for i in range(len(A)):
    sA[A[i]] = True
for i in range(len(B)):
    sB[B[i]] = True


for i in range(MAX, 0, -1):
    in_A = sA[i]
    in_B = sB[i]
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        result %= mod
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        result %= mod
        B_F_cnt += 1
    else:
        coef = ( ( A_F_cnt * B_F_cnt )%mod - (N*M - i) )
        if coef < 0:
            coef += mod
        result *= coef
        result %= mod
        
    # print(in_A, in_B, A_F_cnt, B_F_cnt, result)

print(result % mod)


Measured memory_bytes: 116040
using System;
using System.Collections.Generic;

namespace AtCoderTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int weaponCount = int.Parse(input[0]);
            int hp = int.Parse(input[1]);
     //       List<int> hitDamageList = new List<int>();
            List<int> throwDamageList = new List<int>();
            int maxHitDamage = 0;
            int turnCount = 0;
            int damage = 0;

            for (int i = 0; i < weaponCount; i++)
            {
                string[] str = Console.ReadLine().Split(' ');
         //       hitDamageList.Add(int.Parse(str[0]));
                throwDamageList.Add(int.Parse(str[1]));
                if (maxHitDamage < int.Parse(str[0]))
                {
                    maxHitDamage = int.Parse(str[0]);
                }
            }

            throwDamageList.Sort();

            for (int i = weaponCount - 1; i >= 0; i--)
            {
                if (throwDamageList[i] < maxHitDamage)
                {
                    break;
                }
                damage += throwDamageList[i];
                turnCount++;
                if (hp - damage <= 0)
                {
                    break;
                }
            }

            if (hp - damage > 0)
            {
                double hitTurnCount = 1.0 * (hp - damage) / maxHitDamage;
                hitTurnCount = Math.Ceiling(hitTurnCount);
                turnCount = turnCount + (int)hitTurnCount;
            }

            Console.WriteLine(turnCount);
    //        Console.ReadLine();

        }
    }
}

Measured memory_bytes: 17308
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

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 ll INF=1e9+7;

int main(){
    ll n,a,b;
    cin >> n >> a >> b;
    cout << min(a,b) << " " << max(a+b-n,0LL) << endl;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1E9 + 7;
const int INF = 1 << 29;

int main() {
  string s;
  cin >> s;
  int n = s.length();
  reverse(s.begin(), s.end());
  vector<int> cnt(2019);
  int m = 0;
  int x = 1;
  int ans = 0;
  rep(i, n) {
    cnt[m]++;
    m += ((s[i] - '0') * x);
    m %= 2019;
    x = x * 10 % 2019;
    ans += cnt[m];
  }
  cout << ans << endl;
  return 0;
}


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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;
}

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


void solve(){
    ll n,m,s;
    cin>>n>>m>>s;
    Graph g(n);
    Array a(m),b(m);
    REP(i,m){
        ll u,v;
        cin>>u>>v>>a[i]>>b[i];
        u--;v--;
        add_edge(g,u,v,i,true,i);
    }
    Array c(n),d(n);
    REP(i,n) cin>>c[i]>>d[i];

    ll coin = 50*n;
    vvec<ll> dp(n+1,vec<ll>(coin+1,INF));
    dp[0][min(s,coin)] = 0;

    priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll>>, greater<tuple<ll,ll,ll>>> q;
    q.push({0,min(s,coin),0});//分数、銀貨、開始地点

    while (q.size()) {
        auto [dd,cc,v] = q.top();
        q.pop();
        if (dp[v][cc] < dd)continue;
        dp[v][cc]=dd;
        if(cc!=coin && dp[v][min(cc+c[v],coin)] > dd+d[v]){
            dp[v][min(cc+c[v],coin)]=dd+d[v];
            q.push({dd+d[v],min(cc+c[v],coin),v});
        }
        for(auto e:g[v]){
            if(cc >= a[e.cap] && dp[e.to][cc-a[e.cap]] > dd+b[e.cap]){
                dp[e.to][cc - a[e.cap]] = dd+b[e.cap];
                q.push({dd+b[e.cap],cc-a[e.cap],e.to});
            }
        }
    }
    rep(i,1,n){
        ll ans=INF;
        REP(j,coin+1) chmin(ans,dp[i][j]);
        cout<<ans<<en;
    }

}

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

    solve();
    //ll t;cin>>t;REP(i,t) solve();

    return 0;
}

Measured memory_bytes: 7352
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <unordered_map>
#include <queue>
#include <set>

using namespace std;

#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;


int main(){
    string s;
    cin >> s;
    vector<vector<ll> > dp(s.length() + 1, vector<ll>(13, 0));
    vector<ll> memory(s.length());
    memory[s.length() - 1] = 1;
    ll tmp;
    for (int i = s.length() - 1; i >= 0; i--){
        if (i != s.length() - 1) memory[i] = (memory[i + 1] * 10) % 13;
        if (s[i] == '?'){
            rep(j, 10){
                tmp = (memory[i] * j) % 13LL;
                if (i == s.length() - 1) dp[i][tmp] = 1;
                else rep(k, 13) {
                    dp[i][(tmp + k) % 13] += dp[i + 1][k];
                    dp[i][(tmp + k) % 13] %= mod;
                }
            }
        }
        else {
            tmp = (memory[i] * (int)(s[i] - '0')) % 13LL;
            if (i == s.length() - 1) dp[i][tmp] = 1;
            else rep(k, 13) {
                    dp[i][(tmp + k) % 13] += dp[i + 1][k];
                    dp[i][(tmp + k) % 13] %= mod;
                }
        }
    }
    cout << dp[0][5] << endl;
    return 0;
}




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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    int count = 0;
    int best;
    for(int i = 0;i < S.size();i++){
        if(S.at(i) == 'E'){
            count++;
        }
    }
    best = count;
    for(int i = 0;i < S.size();i++){
        if(S.at(i) == 'E'){
            count--;
            best = min(best,count);
        }
        else{
            count++;
        }
    }
    cout << best << endl;
}


Measured memory_bytes: 720
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
#include <algorithm>
#include <functional>
//#include<stdlib.h>
using namespace std;
int main() {
	int n,x=0,t=0,l=0;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	std::sort(a.begin(), a.end());
	while (true)
	{
		for (int i = 1; i < n; i++)
		{
			a[i] %= a[0];
		}
		std::sort(&a[0], &a[n-1]+1);
		x = 0; t = 0;
		for (int i = 0; i < n; i++)
		{
			if(t!=a[i])
			{
				a[x] = a[i];
				x++;
				t = a[i];
			}
		}
		if (a[0] == 1) { cout << 1; break; }
		else if (n==1) { cout << a[0]; break; }
		n = x;
	}
	return 0;
}

Measured memory_bytes: 640
N=int(input())
an=list(map(int, input().split()))

from collections import Counter
counter = Counter(an)

sc = sorted([(a, c) for a, c in counter.most_common() if c >= 2], key=lambda ac: ac[0], reverse=True)
if len(sc) < 2:
    print(0)
elif sc[0][1] >= 4:
    print(sc[0][0] ** 2)
else:
    print(sc[0][0] * sc[1][0])


Measured memory_bytes: 21384
N=int(input())
sets=[]
if N%2==1:
    sets.append([N])
    for i in range(1,N//2+1):
        sets.append([i,(N-i)])
else:
    for i in range(1,N//2+1):
        sets.append([i,N+1-i])
#print(sets)
path=[]
for i in range(len(sets)):
    for j in range(i+1,len(sets)):
        for k in sets[i]:
            for l in sets[j]:
                path.append([min(k,l),max(k,l)])
#print(path)
print(len(path))
for i in path:
    print(*i)


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

typedef long long ll;

#define rep(i, n) for (int i = 0; i < (ll)n; ++i)
#define repr(i, n) for (int i = n - 1; i >= 0; --i)
#define INF 10e7
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
using namespace std;

void solve(void)
{
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n - h + 1) * (n - w + 1) << endl;
}

int main(void)
{
    solve();
}

Measured memory_bytes: 3588
#include<stdio.h>
int main()
{
	char S[4];
	scanf("%s",S);
	int B=0;
	for(int i=0;i<3;i++)
	{
		if(S[i]==S[i+1])B=1;
	}
	printf("%s\n",B? "Bad":"Good");
	return 0;
}

Measured memory_bytes: 128
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

ans = 'Yes'
time = 0
for ab in AB:
    a,b = ab[0], ab[1]
    time += a
    if time > b:
        ans = 'No'

print(ans)


Measured memory_bytes: 88408