akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");
 
private:
	using ll = long long;
 
	int v;
 
	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}
 
public:
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
 
	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}
 
	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}
 
	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<int(1e9) + 7>;

using ll = long long;

const int MAXN = 2010;
int N, K;
int A[MAXN];

num c2(ll n) {
	return num(n) * (n-1) / 2;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	num ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (A[i] > A[j]) {
				ans += K;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (A[j] < A[i]) {
				ans += c2(K);
			}
		}
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 100005
#define last 1000000000005
 
int max(int a,int b,int c){
    a = (a>b)?a:b;
    a = (a>c)?a:c;
    return a;
} 
int main(){
    int n;
    cin>>n;
    int a[n][3];

    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++)
        {   cin>>a[i][j];   }
    }
    int dp[n][3];
    memset(dp,0,sizeof(dp));
    
    dp[0][0] = a[0][0];
    dp[0][1] = a[0][1];
    dp[0][2] = a[0][2];

    for(int i=1;i<n;i++){

        dp[i][0] = a[i][0] + max(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = a[i][1] + max(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = a[i][2] + max(dp[i-1][0], dp[i-1][1]);
        
    }
    

    cout<<max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]))<<endl;

    return 0;
}

Measured memory_bytes: 2560
from itertools import product

n,m = map(int, input().split())
ks = []
for _ in range(m):
    sl = list(map(int, input().split()))
    ks.append(sl[1:])

pl = list(map(int, input().split()))


ans = 0
pattern = 2
ite = product(range(pattern),repeat=n)
for it in ite:
    s_on_off = list(it)
    for bulb, p in zip(ks, pl):
        curr_cnt = 0
        for s in bulb:
            if s_on_off[s-1] == 1: curr_cnt+=1
        if curr_cnt%2 != p:
            break
    else:
        ans += 1

print(ans)

Measured memory_bytes: 74084
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n) ; ++i)
using namespace std;
using ll = long long;
void self_max(int &a,int b){
  a = max(a,b);
}

int main(){
  string s; cin >> s;
  int arr[26] = {};

  rep(i,4){
    arr[s[i]- 'A']++;
  }

  int ans = 0;
  rep(i,26){
    if(arr[i] == 2) ans++;
  }

  if(ans == 2) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
cnt = 0
ans = n-1
for i in range(n-1):
    if li[i] < li[i+1]:
        cnt += 1
    else:
        ans = min(ans,n-1-cnt)
        cnt = 0
ans = min(ans,n-1-cnt)
print(ans)

Measured memory_bytes: 70936
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){
    //int i,j,k;
    unsigned long long L,R,i,j,k,min = 2020,I,J,temp;
  
    scanf("%lld %lld",&L,&R);
    
    if(R-L >= 2019){
        printf("0");
        return 0;
    }
    L = L % 2019;
    R = R % 2019;
    if(R == 0){
        printf("0");
        return 0;
    }
    if(L >= R) R += 2019;
    for(i = L;i < R;i++){
        for(j = i + 1;j <= R;j++){
            temp = (i*j) % 2019;
            if(temp < min){
                min = temp;
            }
        }
    }
    
    printf("%lld\n",min);
    
    return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}

   

int main(){
    lint N,A;
    lint ans=0;
    cin>>N;
    bool c[N];
   lint tf[15][15];
    lint h=0;
    rep(i,15){
        rep(j,15){
            tf[i][j]=-1;
        }
    }
    rep(i,N){
            cin>>h;
        rep(j,h){
                lint g,f;
                cin>>g>>f;
            tf[i][g-1]=f;
           
        }
    }
    
      rep(i,1<<N){
        lint count=0;
       
        rep(j,N){
            if(i&1<<j){c[j]=true;
           count++;
            }
            else c[j]=false;
        }
        rep(k,N){
            if(c[k]==false)continue;
            rep(l,N){
                    if(tf[k][l]==-1)continue;
                    if(tf[k][l]==1&&c[l]==true)continue;
                      if(tf[k][l]==1&&c[l]==false)count=0;
                        if(tf[k][l]==0&&c[l]==true)count=0;
                          if(tf[k][l]==1&&c[l]==true)continue;
            }
        }
        ans=max(ans,count);
      }
cout<<ans;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _cin      ios_base::sync_with_stdio(0);  cin.tie(0);
#define READ      freopen("input.txt", "r", stdin);
#define WRITE     freopen("output.txt", "w", stdout);
#define endl "\n"
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define repd(i,a,b) for(ll i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define vvll vector<vector<ll> >
#define vll vector<ll>
#define mll map<ll,ll>
#define sz(x) (ll)x.size()
#define sll set<ll>
#define pll pair<ll,ll>
#define F first
#define S second
const ll MAX = 1000004;
const ll INF = 1e18L + 5;


int main() {

	_cin
	// READ
	// WRITE
	ll n;
	cin >> n;
	double p_h[n + 1];
	rep(i, 1, n + 1) cin >> p_h[i];
	vector<vector<double>> dp(n + 1, vector<double> (n + 1, 0.0));
	dp[0][0] = 1.0;
	rep(i, 1, n + 1) {
		rep(j, 0, n + 1) {
			if (j == 0) dp[i][j] = dp[i - 1][j] * (1 - p_h[i]);
			else {
				dp[i][j] = dp[i - 1][j] * (1 - p_h[i]) + dp[i - 1][j - 1] * p_h[i];
			}
		}
	}
	double answer = 0;

	rep(i,0,n+1){
		ll t=n-i;
		if(i>t) answer+= dp[n][i];

	}

	 std::cout << std::setprecision(10) << answer << '\n';



}

Measured memory_bytes: 73772
#include <iostream>
 
int main(void){
 
	int W, _a, _b;
 
	std::cin >> W >> _a >> _b;
 
	int a = (_a<_b) ? _a:_b;
	int b = (_a>_b) ? _a:_b;
 
	int r = (b-a-W);
 
	std::cout << ((r>0)?r:0) << '\n';
 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define deb(x) cout << #x << "=" << x << endl
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
int M=1e9+7,N=205001;

int mm(int x,int y){x%=M,y%=M;return (x*y)%M;}//Modular Multiply
int po(int x,int y){ if(!y)return 1;int a=po(x,y/2)%M;if(y%2)return mm(a,mm(a,x));return mm(a,a);}//(x**y)%M



void solve() {
	int x,y,ans;
	cin>>x>>y;
	if((y-2*x)%2==0 and (4*x-y)%2==0 and y>=2*x and 4*x>=y) cout<<"Yes";
	else cout<<"No";
}


signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}





Measured memory_bytes: 3612
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int c[10][10];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        string s = to_string(i);
        c[s[0]-'0'][s.back()-'0']++;
    }
    int ans = 0;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            ans += c[i][j]*c[j][i];
        }
    }
    cout << ans << endl;
}


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

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

    int N, M;
    cin >> N >> M;
    int a = 1;
    int b = a + M;
    int c = b + 1;
    int d = c + M - 1;
    for (int i = 0; i < M; ++i) {
        if (i % 2 == 0) {
            cout << a << ' ' << b << endl;
            a++;
            b--;
        } else {
            cout << c << ' ' << d << endl;
            c++;
            d--;
        }
    }

    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
 
using namespace std;
 
#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vvii vector<vector<pair<int, int>>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'
 
constexpr int INF = 2e18;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 3;
 
// Asymptotic complexity: O(n log n).
struct pto {
  double x, y;
  bool operator<(const pto &p) const {
    return x < p.x || (x == p.x && y < p.y);
    /* a impressao será em prioridade por mais a esquerda, mais
       abaixo, e antihorário pelo cross abaixo */
  }
};
 
double cross(const pto &O, const pto &A, const pto &B) {
  return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
 
vector<pto> convex_hull(vector<pto> P) {
  int n = P.size(), k = 0;
  vector<pto> H(2 * n);
  // Sort points lexicographically
  sort(P.begin(), P.end());
  // Build lower hull
  for (int i = 0; i < n; ++i) {
    // esse <= 0 representa sentido anti-horario, caso deseje mudar
    // trocar por >= 0
    while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0)
      k--;
    H[k++] = P[i];
  }
  // Build upper hull
  for (int i = n - 2, t = k + 1; i >= 0; i--) {
    // esse <= 0 representa sentido anti-horario, caso deseje mudar
    // trocar por >= 0
    while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0)
      k--;
    H[k++] = P[i];
  }
  H.resize(k);
  /* o último ponto do vetor é igual ao primeiro, atente para isso
  as vezes é necessário mudar */
  return H;
}
 
int mh(pto a, pto b) { return abs(a.x - b.x) + abs(a.y - b.y); }
 
// #define MULTIPLE_TEST_CASES
void solve() {
  int n;
  cin >> n;
 
  vector<pto> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i].x >> v[i].y;
  }
 
  v = convex_hull(v);
 
  int ans = 0;
  for (int i = 0; i < v.size(); ++i) {
    for (int j = 0; j < v.size(); ++j) {
      ans = max(ans, mh(v[i], v[j]));
    }
  }
  cout << ans << endl;
}
 
signed main() {
  // freopen(".in", "r", stdin);
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
 
  int t = 1;
#ifdef MULTIPLE_TEST_CASES
  cin >> t;
#endif
  while (t--)
    solve();
}

Measured memory_bytes: 15952
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    int N = Integer.parseInt(S[0]);
    int M = Integer.parseInt(S[1]);
    int[] balls = new int[N];
    boolean[] check = new boolean[N];
    check[0] = true;
    
    for(int i = 0; i < N; i++){
      balls[i] = 1;
    }
    
    for(int i = 0; i < M; i++){
      String[] T = sc.nextLine().split(" ");
      int A = Integer.parseInt(T[0]);
      int B = Integer.parseInt(T[1]);
      
      balls[A-1]--;
      balls[B-1]++;
      if(check[A-1]){
        check[B-1] = true;
      }
      if(balls[A-1] == 0){
        check[A-1] = false;
      }
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
      if(balls[i] > 0 && check[i]){
        ans++;
      }
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 112896
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
int N, P; long long a[100009], b[100009], c[100009];
int main() {
	cin >> N >> P;
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
		a[i] *= 100 - P;
		b[i] *= P;
		c[i] = a[i] + b[i];
	}
	sort(c, c + N);
	reverse(c, c + N);
	long long sum = 0;
	for (int i = 0; i < N; i++) sum -= b[i];
	for (int i = 0; i < N; i++) {
		sum += c[i];
		if (sum >= 0) {
			cout << i + 1 << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 2560
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
using namespace std;
#define ss second
#define ff first
int32_t main()
{
    fastio;
    int T,n,m,i,j,k,a,b,c;
    T=1;
    string str;
    while(T --> 0)
    {
        cin>>n>>str;
        vector<int> R,G;
        unordered_map<int,bool> B;
        for(i=0;i<n;i++)
        if( str[i] == 'R')
            R.emplace_back(i);
        else if( str[i] == 'G')
            G.emplace_back(i);
        else
            B[i]=true;
 
        m=B.size();
        int ans=R.size()*G.size()*m;
        for(auto a:R)
        for(auto b:G)
        {
            if( (a+b)%2==0 and B[(a+b)/2] )
                ans--;
            if( B[2*a-b])
                ans--;
            if( B[2*b-a])
                ans--;
        }
        cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 4192
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

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

int N, c[11234], a[11234], b[11234];
vector<vector<int>> E;

int main() {

	scanf("%d", &N);
	E.resize(N + 1);
	rep(i, N - 1) {
		scanf("%d %d", &a[i], &b[i]);
		E[a[i]].push_back(b[i]);
		E[b[i]].push_back(a[i]);
	}
	rep(i, N) scanf("%d", &c[i]);
	rep(i, N) c[i] = -c[i];
	sort(c, c + N);
	rep(i, N) c[i] = -c[i];

	int S = 0, Si = 0;
	rep(i, N + 1) {
		if (E[i].size() > S) {
			S = E[i].size();
			Si = i;
		}
	}

	priority_queue<pair<int, int>> pq;
	pq.push({ S, Si });

	int ci = 0;
	int Ans[11234];
	memset(Ans, 0xFF, sizeof(Ans));
	Ans[Si] = c[ci];
	ci++;

	while (!pq.empty()) {
		auto t = pq.top();
		pq.pop();
		vector<pair<int, int>> vtx;
		for (auto v : E[t.second]) {
			vtx.push_back({ -(int)E[v].size(), v });
		}
		sort(vtx.begin(), vtx.end());
		for (auto v : vtx) {
			if (Ans[v.second] == -1) {
				Ans[v.second] = c[ci];
				ci++;
				v.first = -v.first;
				pq.push(v);
			}
		}
	}

	int ans = 0;
	rep(i, N - 1) {
		ans += min(Ans[a[i]], Ans[b[i]]);
	}
	printf("%d\n", ans);
	rep(i, N) printf("%d ", Ans[i + 1]);

	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
const long double eps = 1e-10;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int n;
VL a;
vector<VL> memo;
ll solve(int l, int r) {
    if (memo[l][r] != -1)return memo[l][r];
    if (l == r)return 0LL;

    ll ret = LLINF;
    FOR(i, l, r)chmin(ret, solve(l, i) + solve(i + 1, r));

    return memo[l][r] = ret + a[r] - (0 < l ? a[l - 1] : 0LL);
}

int main() {
    init();

    cin >> n;
    a.resize(n); cin >> a;
    FOR(i, 1, n)a[i] += a[i - 1];
    memo = defvec<ll>(-1, n, n);
    cout << solve(0, n - 1) << "\n";
}


Measured memory_bytes: 1536
import java.util.*;

public class Main{
	Scanner sc = new Scanner(System.in);
	HashMap<String, Integer> data,memo;
	C [] table;
	
	class C{
		String after;
		ArrayList<String> material;
		public C(String after, ArrayList<String> material) {
			this.after = after;
			this.material = material;
		}
		
	}
	
	private void doit(){
		while(true){
			int n = sc.nextInt();
			if(n == 0) break;
			data = new HashMap<String, Integer>();
			memo = new HashMap<String, Integer>();
			for(int i = 0; i < n; i++){
				String s = sc.next();
				int price = sc.nextInt();
				data.put(s, price);
			}
			int k = sc.nextInt();
			table = new C[k];
			for(int i = 0; i < k; i++){
				String af = sc.next();
				int t = sc.nextInt();
				ArrayList<String> list = new ArrayList<String>();
				while(t-- > 0){
					list.add(sc.next());
				}
				table[i] = new C(af, list);
			}
			String target = sc.next();
			int res = dfs(target);
			System.out.println(res);
		}
	}

	private int dfs(String target) {
		if(memo.containsKey(target)){
			return memo.get(target);
		}
		int res = 1 << 24;
		if(data.containsKey(target)){
			res = data.get(target);
		}
		for(int i = 0; i < table.length; i++){
			if(table[i].after.equals(target)){
				int nowsum = 0;
				for(int j = 0; j < table[i].material.size(); j++){
					nowsum += dfs(table[i].material.get(j));
				}
				res = Math.min(res, nowsum);
			}
		}
		memo.put(target, res);
		return res;
	}

	private void debug(Object... o) { System.out.println("debug = " + Arrays.deepToString(o)); }

	public static void main(String[] args) {
		new Main().doit();
	}
}

Measured memory_bytes: 24780
#include <iostream>
#include <vector>
using namespace std;
int main(){
    long n;
    cin>>n;
    long s=0;
    for(long i = 1; n>=i;i=i*10) {
    	s+= (n/i)%10;
    	}
    if(n%s==0) cout << "Yes"<< endl;
    else cout << "No"<< endl;
    return 0;
}

Measured memory_bytes: 256
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

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

public class Main {

	static final int MOD = 1000000007;

	static int sub(int a, int b) {
		int res = a - b;
		return res < 0 ? res + MOD : res;
	}

	static int mul(int a, int b) {
		int res = (int) ((long) a * b % MOD);
		return res < 0 ? res + MOD : res;
	}

	static void solve() throws Exception {
		int n = scanInt();
		String s = scanString();
		int c[] = new int[26];
		for (int i = 0; i < n; i++) {
			++c[s.charAt(i) - 'a'];
		}
		int ans = 1;
		for (int i = 0; i < 26; i++) {
			ans = mul(ans, c[i] + 1);
		}
		out.print(sub(ans, 1));
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 22992
s = input()
ap = 0
zp = len(s)
for i in range(len(s)):
    if s[i] == 'A':
        ap = i
        break
    
for i in range(len(s)):
    if s[len(s)-i-1] == 'Z':
        zp = len(s)-i-1
        break

print(zp-ap+1)
    

Measured memory_bytes: 3516
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, A, B, C, D, E):
    tmp = min(A, B, C, D, E)
    tmp, tmp2 = divmod(N, tmp)
    tmp += 0 if tmp2 == 0 else 1
    print(tmp + 4)


if __name__ == '__main__':
    N = int(input())
    A = int(input())
    B = int(input())
    C = int(input())
    D = int(input())
    E = int(input())
    solve(N, A, B, C, D, E)

    # # test
    # from random import randint
    # from func import random_str
    # solve()


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

int main()
{
  int x1,x2,x3,x4,x5,ans;
  
  cin >> x1 >> x2 >> x3 >> x4 >> x5;
  
  ans=0;
  if (x1==0) ans=1;
  if (x2==0) ans=2;
  if (x3==0) ans=3;
  if (x4==0) ans=4;
  if (x5==0) ans=5;

  cout << ans << endl;
}

Measured memory_bytes: 3564
# B - Papers, Please
# https://atcoder.jp/contests/abc155/tasks/abc155_b

n = int(input())
a = list(map(int, input().split()))

even = 0
cnt = 0

for i in a:
    if i % 2 == 0:
        even += 1
        if i % 3 == 0 or i % 5 == 0:
            cnt += 1

if even == cnt:
    print('APPROVED')
else:
    print('DENIED')


Measured memory_bytes: 9128
#include <cstdio>

char s[55];
int main()
{
	int n;
	scanf("%d%s", &n, s);
	int ans = 0;
	for (int i = 0; i < n - 2; ++i)
	{
		if ((*(unsigned int*)(s + i) & 0xFFFFFF) == 0x434241)
		{
			ans += 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}


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

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> vec(H+1,vector<char>(W+1));
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cin >> vec.at(i).at(j);
    }
  }
  
  for(int i=0; i<H; i++){
    vec.at(i).at(W) = '#';
  }
  for(int i=0; i<W; i++){
    vec.at(H).at(i) = '#';
  }
  
  vector<vector<int>> ans(H+1,vector<int>(W+1));
  
  for(int i=0; i<H+1; i++){
    int cnt = 0;
    int begin = 0;
    bool block = true;
    for(int j=0; j<W+1; j++){
      if(vec.at(i).at(j) == '.'){
        if(block){
          begin = j;
          cnt = 0;
          block = false;
        }
        else{
          cnt++;
        }
      }
      else{
        for(int k=begin; k<=begin+cnt; k++){
          ans.at(i).at(k) += cnt;
        }
        cnt = 0;
        block = true;
      }
    }
  }
  
  
 for(int i=0; i<W+1; i++){
    int cnt = 0;
    int begin = 0;
    bool block = true;
    for(int j=0; j<H+1; j++){
      if(vec.at(j).at(i) == '.'){
        if(block){
          begin = j;
          cnt = 0;
          block = false;
        }
        else{
          cnt++;
        }
      }
      else{
        for(int k=begin; k<=begin+cnt; k++){
          ans.at(k).at(i) += cnt;
        }
        cnt = 0;
        block = true;
      }
    }
  }
  
  int max_lamp = 0;
  
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      max_lamp = max(max_lamp,ans.at(i).at(j));
    }
  }
  cout << max_lamp + 1 << endl;
}

Measured memory_bytes: 19968
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  ll x,y; cin >> x >> y;
  ll temp = x;
  ll res = 0;
  while(temp<=y){
    res++;
    temp*=2;
  }
  cout << res << endl;
  return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N;
    cin >> N;
    vector<int> H(N);
    rep(i, N) cin >> H[i];
    int ans = 0;
    int pre = -1;
    int tmp = 0;
    rep(i, N) {
        int h = H[i];
        if (h <= pre) {
            tmp++;
        } else {
            ans = max(ans, tmp);
            tmp = 0;
        }
        pre = h;
    }
    cout << max(ans, tmp) << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

int n,w;
int v[111];
int h[111];
int vmax,hmax;

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n>>w;
		if(n==0)break;
		hmax=0; vmax=0;
		rep(i,n){
			cin>>v[i];
			maxch(vmax,v[i]/w);
		}
		memset(h,0,sizeof(h));
		rep(i,vmax+1){
			rep(j,n){
				if(i<=v[j]/w&&v[j]/w<(i+1)){
					h[i]++;
				}
			}
		}
		rep(i,vmax+1)maxch(hmax,h[i]);
		double res=0;
		rep(i,vmax+1){
			res+=((double)h[i]/(double)hmax)*((double)(vmax-i)/(double)(vmax));
		}
		printf("%.10f\n", res+0.01);
	}
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	long long int a[n];
	long long int ans = 1;
	for (int i = 0; i < n; i++) {
		cin >> a[i];

	}
	int f = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			cout << 0 << endl;
			return 0;
		}else if (1000000000000000000 / ans < a[i]) {
			f = 1;
		} else {
			ans *= a[i];
		}
	}
	if (f == 1) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
	return 0;
}


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

int n, m, q;
vector<int> a;
vector<int> b;
vector<int> c;
vector<int> d;

vector<int> v;
int ans;

void check() {
  int sum = 0;
  for (int i = 0; i < q; ++i) {
    if (v[b[i]] - v[a[i]] == c[i]) sum += d[i];
  }
  ans = max(ans, sum);
}

void dfs(int depth) {
  if (depth == n) {
    check();
    return;
  }
  int start;
  if (v.empty()) {
    start = 1;
  } else {
    start = v[depth - 1];
  }
  for (int i = start; i <= m; ++i) {
    v.push_back(i);
    dfs(depth + 1);
    v.pop_back();
  }
}

int main() {
  cin >> n >> m >> q;
  a.resize(q);
  b.resize(q);
  c.resize(q);
  d.resize(q);
  for (int i = 0; i < q; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    --a[i];
    --b[i];
  }
  dfs(0);
  cout << ans << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
using namespace std;
using ll = long long;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), b(n), c(n);
    ll i;
    for(i = 0; i < n; i++){
        ll inp;
        cin >> inp;
        a.at(i) = inp;
    }
    for(i = 0; i < n; i++){
        ll inp;
        cin >> inp;
        b.at(i) = inp;
    }
    for(i = 0; i < n; i++){
        ll inp;
        cin >> inp;
        c.at(i) = inp;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    ll count = 0;
    for(i = 0; i < n; i++){
        ll b0 = b.at(i);
        auto ita = lower_bound(a.begin(), a.end(), b0) - 1;
        auto itc = upper_bound(c.begin(), c.end(), b0);
        ll na = ita - a.begin();
        ll nc = c.end() - itc;
        if(*ita < b0 && b0 < *itc) count += (na + 1) * (nc);
    }
    cout << count << endl;
  	return 0;
}


Measured memory_bytes: 5552
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積）
)
A = list(map(int, input().split()))

ans = float('inf')
for a1, a2, a3 in permutations(A, 3):
    tmp = abs(a2-a1)+abs(a3-a2)
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#define ll int64_t
#define REP(i, n) for (ll i=0; i<n; i++)
using namespace std;

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

    ll N, M;
    cin >> N >> M;
    vector<vector<pair<ll, ll>>> graph(N, vector<pair<ll, ll>>());
    REP (i, M) {
        ll l, r, d;
        cin >> l >> r >> d;
        l--; r--;
        graph[l].push_back(make_pair(r, d));
        graph[r].push_back(make_pair(l, -1 * d));
    }

    // for (auto e : graph) {
    //     for (auto f : e) {
    //         cout << f.first << " " << f.second << "\n";
    //     }
    //     cout << "next\n";
    // }

    const ll inf = 10000000000;

    // 値を決めていく
    vector<ll> dist(N, inf);
    // for (auto e : dist) {
    //     cout << e << "\n";
    // }
    REP (i, N) {
        if (dist[i] == inf) {
            dist[i] = 0;
            queue<ll> q;
            q.push(i);
            while (!q.empty()) { 
                ll t = q.front();
                q.pop();
                for (auto e : graph[t]) {
                    if (dist[e.first] != inf) continue;
                    else {
                        // cout << e.first << " dist[e.first]=" << dist[e.first];
                        // cout << " dist[t]=" << dist[t];
                        // cout << " dist[e.second]=" << dist[e.second] << endl;
                        dist[e.first] = dist[t] + e.second;
                        // cout << e.first << " dist[e.first]=" << dist[e.first] << "\n";
                        q.push(e.first);
                    }
                }
            }
        }
    }

    // for (auto e : dist) {
    //     cout << e << "\n";
    // }

    REP (i, N) {
        REP (j, graph[i].size()) {
            if (dist[graph[i][j].first] - dist[i] != graph[i][j].second) {
                cout << "No" << "\n";
                return 0;
            }
        }
    }

    cout << "Yes\n";
}

Measured memory_bytes: 14080
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<numeric>
#include<map>
using namespace std;
 
int main(void)
{
	int N;
	cin >> N;
 
	vector<int> A(N);
	for(int i=0; i<N; i++)
		cin >> A[i];
 
	if(A[0] != 0){
		cout << -1 << endl;
		return 0;
	}
	for(int i=0; i<N-1; i++){
		if(A[i+1]>A[i]+1){
			cout << -1 << endl;
			return 0;
		}
	}
 
	map<int, int> mp;
	for(int i=0; i<N; i++){
		int seed = i - A[i];
 
		//if(seed < 0 || (i>0 && A[i]>A[i-1]+1)){
		//	cout << -1 << endl;
		//	return 0;
		//}
 
		mp[seed] = i - seed;
	}
 
	long long ret = 0;
	for(auto it=mp.begin(); it!=mp.end(); it++)
		ret += it->second;
 
	cout << ret << endl;
 
	return 0;
}


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

A = []

# 出力を受け取る
for i in range(N):
    Si , Pi = input().split()
    Pi = int(Pi) # 型変換

    A.append([i,Si,Pi])

# リストにアクセス
second = lambda A : A[1]
third = lambda A : A[2]

# ソート
A.sort(key=third,reverse=True)
A.sort(key=second)

for target in A:
    print(target[0] + 1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
int mod =1000000007;
const double PI = acos(-1);
ll lcm(ll x, ll y) { return x / __gcd(x, y) * y; }
void factorization(ll n,map<ll,ll>& mp){
    for(ll i=2;i*i<=n;i++){
        while(n%i==0){
            mp[i]++;
            n /= i;
        }
     }
     if(!(n == 1)) mp[n]++;
}

int main(){
   ll n,p;
   cin>>n>>p;
   map<ll,ll>res;
   factorization(p,res);
   ll ans =1;
   for(auto x:res){
       while(x.second>=n){
           ans*=x.first;
           x.second-=n;
       }
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 3636
N=int(input())
S=input()
flag=False
if N%2!=0:
  print('No')
else:
  for i in range(int(N/2)):
    if S[i]!=S[int(N/2)+i]:
      flag=True
  if flag==True:
    print('No')
  else:
    print('Yes')

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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T>
struct edge {
    int src, to;
    T cost;

    // to, costで初期化
    edge (int to, T cost) : src(-1), to(to), cost(cost) {}

    // src, to, costで初期化
    edge (int src, int to, T cost) : src(src), to(to), cost(cost) {}

    // toにxを代入？
    edge &operator=(const int &x) {
        to = x;
        return *this;
    }
    
    // edge()でtoを返す？
    operator int() const {return to;}
};

// templates
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<Edges<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/*
 * Dijkstra
 * input: WeightedGraph<T> &g: グラフ
 *        int s: 始点
 * output: vector<T>: sから各要素への最短経路長
 */
template<typename T>
vector<T> dijkstra(WeightedGraph<T> &g, int s) {
    vector<T> dist(g.size(), LINF);

    using Pi = pair<T, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    while(!que.empty()) {
        T cost;
        int idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]) {
            auto next_cost = cost + e.cost;
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to], e.to);
        }
    }
    return dist;
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  WeightedGraph<ll> graph(n);
  for(int i=0;i<n-1;++i) {
    int a, b; ll c; cin >> a >> b >> c;
    a--; b--;
    graph[a].push_back(edge<ll>(a, b, c));
    graph[b].push_back(edge<ll>(b, a, c));
  }

  int q, k; cin >> q >> k;
  k--;
  vector<ll> dist = dijkstra(graph, k);
  // printv(dist);
  for(int i=0;i<q;++i) {
    int x, y; cin >> x >> y;
    x--; y--;
    cout << dist[x] + dist[y] << endl;
  }
}


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

int main(){
  int num_1, num_0, num_n1;
  int num;
  cin >> num_1 >> num_0 >> num_n1 >> num;
  int sum = 0;
  
  for(int i = 0; i < num_1; i++){
    num--;
    sum++;
    if(num == 0){
      break;
    }
  }
  
  for(int i = 0; i < num_0; i++){
    num--;
    if(num <= 0){
      break;
    }
  }
  for(int i = 0; i < num_n1; i++){
    if(num <= 0){
      break;
    }
    num--;
    sum--;
    if(num == 0){
      break;
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 3624
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int N; double D,X;

inline int gi()
{
	char ch; int ret = 0,f = 1;
	do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
	if (ch == '-') f = -1,ch = getchar();
	do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
	return ret*f;
}

inline double calc(int n,double d,double x)
{
	if (n == 0) return 0;
	else return calc(n-1,(2*d+2*n*d+5*x)/(2*n),(2*x)/n+x)+d+(2*n-1)*x/2;
}

int main()
{
	//freopen("F.in","r",stdin);
	//freopen("F.out","w",stdout);
	N = gi(); D = gi(); X = gi();
	cout << fixed << setprecision(10) << calc(N,D,X) << endl;
	return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
using namespace std;
 
#define debug(x) cerr<<#x<<" = "<<x<<endl;
 
const int C_MAX = 100;
 
int cards[C_MAX];
 
// [i, i+k)
int point[C_MAX];
 
int main() {
    for(int N, K; cin >> N >> K, N || K;) {
        for(int i = 0; i < N; i++) {
            cin >> cards[i];
        }
 
        point[0] = 1;
        for(int i = 0; i < K; i++) {
            point[0] *= cards[i];
        }
 
        for(int i = 1; i < N - K + 1; i++) {
            point[i] = point[i - 1] / cards[i - 1] * cards[i + K - 1];
        }
 
        int before = *max_element(point, point + N - K + 1);
        int vmax = -1;
 
        for(int x = 0; x < N; x++) {
            for(int y = 0; y < N; y++) {
                if(x == y) continue;
                swap(cards[x], cards[y]);
 
                point[0] = 1;
                for(int i = 0; i < K; i++) {
                    point[0] *= cards[i];
                }
 
                for(int i = 1; i < N - K + 1; i++) {
                    point[i] = point[i - 1] / cards[i - 1] * cards[i + K - 1];
                }
 
                int after = *max_element(point, point + N - K + 1);
                vmax = max(vmax, after);
 
                swap(cards[x], cards[y]);
            }
        }
        if(vmax < before)
            cout << "NO GAME" << endl;
        else {
            cout << vmax - before << endl;
        }
    }
 
    return 0;
}

Measured memory_bytes: 1160
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A.sort(reverse=1)
cur = [A[0]]
nxt = cur[:]
# 作成済を-1とする
A[0] = -1

for _ in range(N):
    j = 0
    for i, a in enumerate(A):
        if a == -1:
            continue
        if a < cur[j]:
            # 大きい要素から順に、まだ作っていない大きい要素を作っていく
            nxt.append(a)
            A[i] = -1
            j += 1
            # この世代は作り終わった
            if j == len(cur):
                break
    else:
        # 子要素を作れない要素があった
        No()
        exit()
    nxt.sort(reverse=1)
    cur = nxt[:]
Yes()


Measured memory_bytes: 34676
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class Data{
public:
	ll first,second,third;
	Data()=default;
	Data(ll a,ll b,ll c):first(a),second(b),third(c){}
};

class ConnectNodeInfo{
	vector<vector<Data>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v,ll w,ll i){
		graph[u].emplace_back(v,w,i);
		graph[v].emplace_back(u,w,i);
	}
	vector<Data>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

int MC=0;
void DFS(ConnectNodeInfo& connect,int child,int parent,int pcolor){
	int c=1;
	for(int j=0,ej=connect[child].size();j<ej;j++){
		int u=child,v=connect[child][j].first;
		if(v==parent){
			connect[child][j].second = pcolor;
		}
		else{
			if(c==pcolor){
				connect[child][j].second=c+1;
				MC = max(MC,c+1);
				c+=2;
			}
			else{
				connect[child][j].second=c;
				MC = max(MC,c);
				c+=1;
			}
			DFS(connect,connect[child][j].first,child,connect[child][j].second);
		}
	}
}

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

	int N=in();
	ConnectNodeInfo connect(N);
	vector<pair<int,int>> P(N-1);
	REP(i,N-1){
		int u=in()-1,v=in()-1;
		P[i].first=u,P[i].second=v;
		connect.AddNonDirectionalConnection(u,v,0,i);
	}
	
	DFS(connect,0,-1,0);
	out(MC);
	vector<int> CA(N-1);
	REP(i,N){
		for(auto& x:connect[i]){
			CA[x.third] = x.second;
		}
	}
	REP(i,N-1){
		out(CA[i]);
	}

	return 0;
}


Measured memory_bytes: 11776
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount
           
#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


int main()
{
    int r, c;
    while (cin >>r >> c, r | c)
	puts(r*c & 1 ? "no" : "yes");
}

Measured memory_bytes: 0