akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <sstream>

#define DEBUG 0
#define fi first
#define se second
#define pb push_back
#define fore(i, a, b) for (int i = (a), _b = (b); i < (_b); ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= (_b); ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= (_b); --i)

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const int INF = 1e9 + 3;
const int MOD = 1e9 + 7;

int main() {
    if (DEBUG) {
        freopen("CP.inp", "r", stdin);
        //freopen("CP.out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vi l(n + 3), r(n + 3), a(n + 3);
    fort(i, 1, n) cin >> a[i];
    fort(i, 1, n) l[i] = max(l[i - 1], a[i]);
    ford(i, n, 1) r[i] = max(r[i + 1], a[i]);
    fort(i, 1, n) cout << max(l[i - 1], r[i + 1]) << '\n';
    return 0;
}


Measured memory_bytes: 3968
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = /*1'000'000'007LL;*/ 998'244'353LL;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int N;
string S[50]; int t[50];
string X;

signed main(){
    cin >> N;
    rep(i, N) cin >> S[i] >> t[i];
    cin >> X;

    int ans = 0;
    bool flg = false;
    rep(i, N){
        if(flg) ans += t[i];
        if(S[i] == X) flg = true;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3580
#109_B
N=int(input())
W=[input() for _ in range(N)]

flg=True
for i in range(N-1):
    if W[i][-1]!=W[i+1][0]:
        flg=False
if len(W)!=len(set(W)):
    flg=False
print('Yes' if flg else 'No')

Measured memory_bytes: 3060
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#include<random>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};


int main(){
//input
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n,a[100010],b[100010];
    ll suma[100010],sumb[100010];
    cin>>n;
    rep(i,n){
        cin>>a[i];
        suma[i+1]=suma[i]+a[i];
    }
    rep(i,n){
        cin>>b[i];
    }
    repr(i,n){
        sumb[i]=sumb[i+1]+b[i];
    }
    ll ans=0;
    rep2(i,1,n+1){
        ans=max(ans,suma[i]+sumb[i-1]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2304
import java.util.*;

public class Main{

    public static void main(String args[]){

        // スキャナーの宣言
        Scanner sc = new Scanner(System.in);
        // 整数の入力
		int a = sc.nextInt();
        // スペース区切りの整数の入力
        int b = sc.nextInt();
        // 文字列の入力
        int c = sc.nextInt();
        int ans;
        if(b / a > c){
            ans = c;
        }else{
            ans = b / a;
        }
        // 出力
        System.out.println(ans);

    }

}

Measured memory_bytes: 21716
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

ll N, W;
ll w[128], v[128];
ll dp[128][512];

int main() {
  cin >> N >> W;
  rep(i, N) cin >> w[i] >> v[i];

  ll sum = 0;
  rep(i, N) {
    ll ww = w[i] - w[0];

    for (int j = i; j >= 0; j--) {
      for (int k = sum; k >= 0; k--) {
        dp[j + 1][k + ww] = max(dp[j+1][k+ww],dp[j][k]+v[i]);
      }
    }
    sum += ww;
  }

  ll ans = 0;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=sum;j++){
      if(w[0]*i+j>W) continue;
        ans = max(ans,dp[i][j]);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
/*
██╗  ██╗ █████╗ ██████╗ ███████╗███████╗███╗   ███╗        ██╗  ██╗██╗  ██╗ █████╗ ██╗     ███████╗██████╗
██║ ██╔╝██╔══██╗██╔══██╗██╔════╝██╔════╝████╗ ████║        ██║ ██╔╝██║  ██║██╔══██╗██║     ██╔════╝██╔══██╗
█████╔╝ ███████║██████╔╝█████╗  █████╗  ██╔████╔██║        █████╔╝ ███████║███████║██║     █████╗  ██║  ██║
██╔═██╗ ██╔══██║██╔══██╗██╔══╝  ██╔══╝  ██║╚██╔╝██║        ██╔═██╗ ██╔══██║██╔══██║██║     ██╔══╝  ██║  ██║
██║  ██╗██║  ██║██║  ██║███████╗███████╗██║ ╚═╝ ██║███████╗██║  ██╗██║  ██║██║  ██║███████╗███████╗██████╔╝
╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚══════╝╚═╝     ╚═╝╚══════╝╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝╚══════╝╚═════╝
Believe in yourself ,( try and try and then try ), You can do it
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
#define endl "\n"
#define Ceil(x,y) ((x+y-1)/y)
#define clr(arr, x) memset(arr, x, sizeof arr)
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define rt(s) return cout<<s,0
#define watch(x) cout<<(#x)<<" = "<<x<<endl
#define sz(s)	(int)(s.size())
#define OO 0x3f3f3f3f3f3f3f3fLL
const int oo = 0x3f3f3f3f, Mod = 1e9 + 7;
using namespace std;
typedef long long ll;
int dx[] { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[] { 0, 0, 1, -1, 1, -1, 1, -1 };
void K_K(){
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif  !ONLINEJUDGE
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int n;
vector<ll>arr;
ll dp[405][405];
ll sol(int l,int r){
	if (l == r)
		return 0;
	ll &ret = dp[l][r];
	if (~ret)
		return ret;
	ret = OO;
	for (int i = l; i < r; i++){
		ret = min(ret, sol(l, i) + sol(i + 1, r) + (arr[r] - arr[l - 1]));
	}
	return ret;
}
int main(){
	K_K();
	cin >> n;
	arr.resize(n + 1, 0);
	clr(dp, -1);
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
		arr[i] += arr[i - 1];
	}
	cout << sol(1, n);
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int W, N, v[1010], w[1010], dp[1010];

int main(void) {
  int ca = 1;
  while (true) {
    cin >> W;
    if(W == 0) break;
    cin >> N;
    REP(i, N) {
      cin >> v[i];
      getchar();
      cin >> w[i];
    }
    REP(i, W+5) dp[i] = 0; 

    for (int i = 0; i < N; i++) {
      for (int j = W; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    }

    int a = -INF, b = 0;
    for (int i = 0; i < W+1; i++) {
      //cout << dp[i] << " ";
      if (a < dp[i]) {
        a = dp[i];
        b = i;
      }
    }
    //cout << endl;
    cout << "Case " << ca << ":" << endl << a << endl << b << endl;
    ca++;
  }
  return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
int main() {
  int x, n; cin >> x >> n;
  set<int> p;
  for (int i = 0; i < n; i++) {
    int pi; cin >> pi;
    p.insert(pi);
  }
  int m1 = numeric_limits<int>::max();
  int m2 = numeric_limits<int>::min();
  for (int k = 0; k <= 100; k++) {
    if (!p.count(x + k))
      m1 = min(m1, k);
    if (!p.count(x - k))
      m2 = max(m2, -k);
  }
  cout << x + (m1 >= abs(m2) ? m2 : m1) << endl;
  return 0;
}

Measured memory_bytes: 3600
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


/* define */
#define Yes(X) puts ( (X) ? "Yes" : "No")
#define YES(X) puts ( (X) ? "YES" : "NO")
#define FOR(i, a, b) for ( int i = (a); i < (b) ; i++)
#define REP(i, n) for ( int i = 0; i < (n) ; i++)
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max3(a, b, c) ((max((a), (b)) > (c)) ? max((a), (b)) : (c))
#define min3(a, b, c) ((min((a), (b)) < (c)) ? min((a), (b)) : (c))

/* const */
const int MOD = 1000000007;

/* alias */
typedef long long ll;
typedef unsigned  u;

/* function */
int cmp(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}
int cmp2(const void *a, const void *b) {
	return *(int*)b - *(int*)a;
}
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
ll Lgcd(ll a, ll b) {
	if (b != 0) return Lgcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
ll Llcm(ll a, ll b) {
	return a / Lgcd(a, b) * b;
}

/* main */

int main() {
	int n, m, ans = 0;
	string s[100], t[100];
	cin >> n;
	REP(i, n) cin >> s[i];
	cin >> m;
	REP(i, m) cin >> t[i];
	REP(i, n) {
		int c = 0;
		REP(j, n) if (s[i] == s[j]) c++;
		REP(j, m) if (s[i] == t[j]) c--;
		ans = max(ans, c);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#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[i].begin(),s[i].end());
    }
    sort(s,s+n);
    long long x=0,p=1;
    for(int i=0;i<n-1;i++){
        if(s[i]==s[i+1])p++;
        else{
            x+=p*(p-1)/2;
            p=1;
        }
    }
    cout<<x+p*(p-1)/2<<endl;
    return 0;
}

Measured memory_bytes: 7296
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 200000
class unionfind
{
public:
	int par[SIZE];
	int ran[SIZE];
	int r1[SIZE], r2[SIZE];
	void init()
	{
		for (int i = 0; i<SIZE; i++)
		{
			par[i] = i;
			ran[i] = 0;
		}
	}
	int find(int a)
	{
		if (a == par[a])return a;
		else return par[a] = find(par[a]);
	}
	void unite(int a, int b)
	{
		a = find(a);
		b = find(b);
		if (a == b)return;
		if (ran[a]>ran[b])
		{
			par[b] = a;
			r1[a] += r1[b];
			r2[a] += r2[b];
		}
		else
		{
			par[a] = b;
			r1[b] += r1[a];
			r2[b] += r2[a];
		}
		if (ran[a] == ran[b])ran[b]++;
	}
};
unionfind uf;
typedef long long ll;
char m[444][444];
int main()
{
	int mx, my;
	scanf("%d%d", &mx, &my);
	for (int i = 0; i < mx; i++)scanf("%s", m[i]);
	uf.init();
	for (int i = 0; i < mx; i++)for (int j = 0; j < my; j++)
	{
		if (m[i][j] == '#')uf.r1[i*my + j]++;
		else uf.r2[i*my + j]++;
	}
	for (int i = 0; i < mx; i++)for (int j = 0; j < my - 1; j++)if (m[i][j] != m[i][j + 1])uf.unite(i*my + j, i*my + j + 1);
	for (int i = 0; i < mx - 1; i++)for (int j = 0; j < my; j++)if (m[i][j] != m[i + 1][j])uf.unite(i*my + j, (i + 1)*my + j);
	ll ans = 0;
	for (int i = 0; i < mx*my; i++)if (uf.find(i) == i)ans += (ll)(uf.r1[i])*(ll)(uf.r2[i]);
	printf("%lld\n", ans);
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n,h; cin >> n >> h;
  int mxa = 0;
  int a[n],b[n];
  REP(i,n) {
    cin >> a[i] >> b[i];
    chmax(mxa, a[i]);
  }

  vector<int> arrb;
  REP(i,n) {
    if (mxa < b[i]) arrb.push_back(b[i]);
  }
  sort(ALL(arrb));

  int ans = 0;
  while(h > 0) {
    if (!arrb.empty()) {
      int v = arrb.back();
      arrb.pop_back();
      h-=v;
      ans++;
    } else {
      ans += h/mxa;
      if (h%mxa) ans++;
      h = 0;
    }
  }

  COUT(ans);
  return 0;
}

Measured memory_bytes: 4672
#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 
#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    visit = []
    while q:
        nh,nw = q.popleft()
        visit.append((nh,nw))
        #徒歩での遷移
        if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
            q.append((nh-1,nw))
            dp[nh-1][nw] = dp[nh][nw]
        if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
            q.append((nh+1,nw))
            dp[nh+1][nw] = dp[nh][nw]
        if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
            q.append((nh,nw-1))
            dp[nh][nw-1] = dp[nh][nw]
        if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
            q.append((nh,nw+1))
            dp[nh][nw+1] = dp[nh][nw]
    while visit:
    #ワープで遷移
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)    
    


Measured memory_bytes: 128192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define L 100003*3
long long dis[L];

void solve(long long N, long long M, std::vector<pair<ll, ll>> Edge, vector<ll> startPos, vector<ll> endPos, long long S, long long T){
    memset(dis, -1, sizeof(dis));
    dis[S] = 0;
    queue<long long> Q;
    Q.push(S);
    while (!Q.empty()) {
        auto v = Q.front();
        Q.pop();
        auto start = startPos[v];
        auto end = endPos[v];
        if (start >= M) continue;
        for (int i = start; i < end; i++) {
            auto s = Edge[i].first;
            auto t = Edge[i].second;
            long long& d = dis[t];
            if (d < 0) {
                Q.push(t);
                d = dis[v] + 1;
            }
        }
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> u(M);
    std::vector<long long> v(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&u[i]); u[i]--;
        scanf("%lld",&v[i]); v[i]--;
    }
    long long S;
    scanf("%lld",&S); S--;
    long long T;
    scanf("%lld",&T); T--;

    std::vector<long long> U(M * 3);
    std::vector<long long> V(M * 3);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < 3; j++) {
            U[i * 3 + j] = u[i] * 3 + j;
            V[i * 3 + j] = v[i] * 3 + (j + 1) % 3;
        }
    }
    
    N *= 3, M *= 3, S *= 3, T *= 3;
    vector<pair<ll, ll>> Edge(M);
    for (int i = 0; i < M; i++) {
        Edge[i] = make_pair(U[i], V[i]);
    }
    sort(Edge.begin(), Edge.end());
    vector<ll> startPos(N);
    vector<ll> endPos(N);
    for (int i = 0; i < N; i++) {
        startPos[i] = M + 1;
        endPos[i] = -1;
    }
    for (ll i = 0; i < M; i++) {
        auto s = Edge[i].first;
        startPos[s] = min(startPos[s], i);
        endPos[s] = max(endPos[s], i + 1);
    }
    solve(N, M, std::move(Edge), std::move(startPos), std::move(endPos), S, T);

    cout << (dis[T] < 0 ? -1 : dis[T] / 3) << endl;
    return 0;
}


Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;
int gcd(int a, int b) {
  if (b == 0) {
	  return a;
	}
  return gcd(b, a % b);
}

int gcd(int a, int b, int c) {
  return gcd(gcd(a, b), c);
}

int main() {
  int k;
  cin >> k;
  ll ans = 0;
  REP1(a, k) {
	REP1(b, k) {
	  REP1(c, k) {
		ans += gcd(a, b, c);
	  }
	}
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,aa,d=0;
  cin>>n;
  n++;
  int a[100001]={};
  for(int i=1;i<n;i++){
    cin>>aa;
    if(aa>100000)
      d++;
    else
      a[aa]++;
  }
  for(int i=1;i<100001;i++){
    if(a[i]>=i)
      d+=a[i]-i;
    else
      d+=a[i];
  }
  cout<<d;
}

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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1 << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) ((n) * ((n) + 1)) / 2
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).push_front(a)
#define eb(x, a) (x).emplace_back(a)
#define F first
#define S second
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class T>
bool chmax(T &a, const T &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int N, K, d;
  cin >> N >> K;
  vector<bool> D(9, true);
  rep(i, 0, K) cin >> d, D[d] = false;

  queue<int> que;
  que.push(0);
  // vector<int> ans;
  while (!que.empty()) {
    int q = que.front();
    que.pop();
    rep(i, 0, 10) if (D[i]) {
      int next = q * 10 + i;
      // cout << next << ' ';
      if (next == 0)
        continue;
      else if (next >= N) {
        // pb(ans, next);
        cout << next << '\n';
        return 0;
      } else
        que.push(next);
    }
    // cout << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i,n) for(int i=0;i<n;++i)
#define rep(j,n) for(int j=0;j<n;++j)
#define REP(i,n) for(int i=1;i<=n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define len(s)   ((int)s.size())
#define F first
#define S second
#define pb push_back
#define pf push_front
#define m_p make_pair
typedef long long ll;
typedef double db;
typedef vector<ll> ve;
typedef vector<pair<int, int> > vepa;
typedef set<string>se;
typedef map<char,int> mpp;
const ll N=3000,OO=1e14,MOD=1e9+7;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
ll TC,n,m,k,a,b,c,x,y,l,r,cnt,sum,mx,mn,arr[N],d[N];
bool f,vis[N];
int main(){
   IOS;
   string s;
   cin>>n;
   if(n==1)cout<<0;
   else cout<<1;

go;
}


Measured memory_bytes: 3652
n = int(input())
pattern = ["S", "H", "C", "D"]

cards = [[False for i in range(13)] for j in range(4)]

cnt = 0
while True:
    if cnt >= n:
        break
    a, b = input().split()
    for i in range(4):
        if a == pattern[i]:
            cards[i][int(b) - 1] = True
    cnt += 1

for i in range(4):
    for j in range(13):
        if cards[i][j] == False:
            print(pattern[i], j + 1)


Measured memory_bytes: 5604
# 12/25 AC日記
# GCDについて,2,3を追加しておくと全体のgcdは必ず1
# つまり残りは2の倍数または3の倍数を入れることにする?
# 2,3,a ではaは素数ではない.また3,(2+a)=3なのでa = 4?と思うが(3+a)は偶数なので7とする?
# 2,3,7に加えるとしたら？->この方法だと20000個数も取れないでしょ
# ちょっと難しいので休憩

# 12/27 再開
# 素因数は必ず2種類あるべきなのではないか
# それを2,3とする
# 0(mod2) ∧ !0(mod3) -> 総和は3の倍数
# 全部入れると丁度2万個なのでこれが想定されていそう
n = int(input())
nn = n
if n == 3:
    print("2 5 63")
else:
    res = [2, 4, 3, 9]
    n -= 4
    for i in range(2, 5001):
        if n < 2:
            break
        else:
            n -= 2
            res.append(6 * i - 4)
            res.append(6 * i - 2)
    for i in range(3, 5000, 2):
        if n < 2:
            break
        else:
            n -= 2
            res.append(6 * i - 3)
            res.append(6 * i + 3)
    for i in range(1, 5001):
        if n == 0:
            break
        else:
            n -= 1
            res.append(6 * i)
    for i in range(len(res)):
        print(str(res[i]) + " ", end="")

Measured memory_bytes: 43752
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

A, B, C, D = mii()

takahasi = True
while A > 0 and C > 0:
    if takahasi:
        C -= B
    else:
        A -= D
    takahasi = not takahasi

if A > 0:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 9348
#include <iostream>
#include <string>
#include <vector>
#include <ios>
#include <iomanip>
#include <stack>
#include <queue>
#include <algorithm>

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

using namespace std;

const int INF = 100000000;

int main(){
  string s;
  cin >> s;
  int size = s.length();
  bool result = true;
  int C_count = 0;
  int cap_count = 0;

  if ((s[0] != 'A') || (s[1] < 97 || 122 < s[1]) || (s[size - 1] < 97 || 122 < s[size - 1])) {
    result = false;
  }
  for (int i = 2; i < size - 1; i++) {
    if (s[i] == 'C') {
      C_count++;
    }
    if (65 <= s[i] && s[i] <= 90) {
      cap_count++;
    }
  }
  if (C_count == 1 && cap_count == 1 && result) {
    cout << "AC" << endl;
    return 0;
  }
  cout << "WA" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

void solve() {
  int a, b, k;
  cin >> a >> b >> k;
  for(int i = 0; i < k; i++) {
    int& from = (i%2==0 ? a : b);
    int& to = (i%2==1 ? a : b);
    if(from%2) from--;
    to += from/2;
    from /= 2;
  }
  cout << a << " " << b << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000000)
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Measured memory_bytes: 155832
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 10000000000000000;
const ll mod = 1000000007;
//printf("%.10f\n", n);
signed main() {
	ll n, m, a = 0, b = 0, cnt = 0, ans = INF; cin >> n;
	vector<ll> v(n);
	for (int h = 0; h < n; h++) {
		cin >> v[h];
	}
	for (int h = -500; h <= 500; h++) {
		cnt = 0;
		for (int i = 0; i < n; i++) {
			cnt += pow(abs(v[i] - h), 2);
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	cin >> n; return 0;
}

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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=200009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}

int tre[4*M+2],lz[4*M+2];
int nxt[M+5];
map<int,int>id;
set<int>s;
int n,d,a;
vector<pi>vec;
void propagate(int pos,int l,int r)
{
    if(lz[pos]==0)return ;
    tre[pos]+=(r-l+1)*lz[pos];
    if(l!=r)
    {
        lz[2*pos]+=lz[pos];
        lz[2*pos+1]+=lz[pos];
    }
    lz[pos]=0;

}
void update(int pos,int l,int r,int I,int J,int val)
{
    propagate(pos,l,r);
    if(l>J || r<I)return;
    if(I<=l && J>=r)
    {
        lz[pos]=val;
        propagate(pos,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    update(2*pos,l,mid,I,J,val);
    update(2*pos+1,mid+1,r,I,J,val);
    tre[pos]=tre[2*pos]+tre[2*pos+1];
}
int qry(int pos,int l,int  r,int I,int J)
{
    propagate(pos,l,r);
    if(l>J || r<I)
    {
        return  0;
    }
    if(I<=l && J>=r)
    {
        return tre[pos];
    }
    int mid=(l+r)>>1;
    int op1=qry(2*pos,l,mid,I,J);
    int op2=qry(2*pos+1,mid+1,r,I,J);
    tre[pos]=tre[2*pos]+tre[2*pos+1];
    return op1+op2;
}

 main()

{
    fast
    cin>>n>>d>>a;
    f(i,1,n)
    {
        int t1,t2;
        cin>>t1>>t2;
        vec.pb(mp(t1,t2));
    }
    sort(vec.begin(),vec.end());
    int j=0;
    int len=2*d;
    vec[n].fi=inf;
    f(i,0,n-1)
    {   j=max(j,i);
        while(1)
        {
            int dis=vec[i].fi+len;
            if(vec[j].fi<=dis)
            {
                j++;
            }
            else break;
        }
        nxt[i]=j-1;
    }
    int ses=0;
    f(i,0,n-1)
    {
        int lft=i;
        int rgt=nxt[i];
        //cout<<nxt[i]<<"#"<<endl;
        int bam=qry(1,0,n-1,i,i);
        if(bam>=vec[i].si)continue;
        int gap=vec[i].si-bam;
        int mov=(gap+a-1)/a;
        int val=mov*a;
        update(1,0,n-1,lft,rgt,val);
        ses+=mov;
    }
    cout<<ses<<endl;




















    return 0;

}













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

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,l,r) for(int i = l; i <= r; i++)
#define TR(e,x) for(auto e = x.begin(); e != x.end(); e++)
#define DEBUG(x) cout << #x << "=" << x << endl;
#define SHOW1(A,n) { REP(i,n-1) printf("%d ", A[i]); printf("%d\n", A[n-1]); }
#define SHOW2(A,m,n) { REP(i,m) { REP(j,n-1) printf("%d ", A[i][j]); printf("%d\n", A[i][n-1]); } }
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)((x).size())
typedef long long LL;
const int MAXN  = 8e5, INF = ~0U>>1, MOD = ~0U>>1;



int main()
{
#ifdef LOCAL
    //freopen("i.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
#endif //LOCAL

    int a, b, c, d;
    scanf("%d%d%d%d", &a,&b,&c,&d);
    puts((fabs(a-b)<=d&&fabs(b-c)<=d) || fabs(a-c)<=d ? "Yes":"No");

    return 0;
}


















































































Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::iter::*;

fn parse_to_array<T:FromStr>(string:&str) -> Vec<T> {
    string.split_whitespace()
        .map(|elem| elem.parse().ok().expect("failed to parse token"))
        .collect()
}

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

fn main() {
    let stdin = stdin();
    let mut input = String::new();
    let N:usize = read();
    stdin.read_line(&mut input).expect("Error");
    let mut v = parse_to_array::<u32>(&input);
    v.sort_by(|a,b| a.partial_cmp(b).unwrap().reverse());

    let sum:f64 = v.iter().enumerate().map(|(i,&v_i)|{
        v_i as f64*(2f64.powf(if i != N-1 {
            -((i+1) as f64)
        }else{ 
            -((N-1) as f64)
        }))
    }).sum();
    println!("{}",sum)
}


Measured memory_bytes: 4476
#include<iostream>
#include<vector>
#include<string>

using namespace std;

void judgeGrade(vector<int>& scores,vector<string>& grades)
{
  if(scores[0]==-1 or scores[1]==-1) grades.push_back("F");
  else if(scores[0]+scores[1]>=80) grades.push_back("A");
  else if(scores[0]+scores[1]>=65) grades.push_back("B");
  else if(scores[0]+scores[1]>=50) grades.push_back("C");
  else if(scores[0]+scores[1]>=30 and scores[2]>=50) grades.push_back("C");
  else if(scores[0]+scores[1]>=30) grades.push_back("D");
  else grades.push_back("F");
}

int main(int argc, char* argv[])
{
  vector<int> scores(3,0);
  vector<string> grades;
  while(1)
  {
    cin >> scores[0] >> scores[1] >> scores[2];
    if(scores[0]==-1 && scores[1]==-1 && scores[2]==-1) break;
    judgeGrade(scores,grades);
  }
  for(string g:grades) cout << g << endl;
}

Measured memory_bytes: 3164
#include<iostream>
using namespace std;
 
class ModInt{
  static const int default_mod = 1e9 + 7;
public:
  ModInt(long long val, int mod)
    : val(val % mod), mod(mod)
  {
  }
  ModInt(long long val)
    : ModInt(val, default_mod)
  {
  }
  ModInt operator* (const ModInt& another){
    return ModInt(val * another.val);
  }
    ModInt operator+ (const ModInt& another){
        return ModInt(val + another.val);
    }
  ModInt& operator*=(const long long rhs){
    this->val *= rhs;
    this->val %= mod;
    return *this;
  }
  
  ModInt pow(long long exponent){
    exponent %= mod;
    if(exponent == 0){
      return ModInt(1, mod);
    }else{
      if(exponent % 2){
        return ((*this) * (*this)).pow(exponent / 2) * (*this);
      }else{
        return ((*this) * (*this)).pow(exponent / 2);
      }
    }
  }
  ModInt inv(){
    return this->pow(mod - 2);
  }
  static ModInt fact(long long n, int mod){
    n %= mod;
    auto ret = ModInt(1, mod);
    while(n > 1){
      ret *= n;
      n--;
    }
    return ret;
  }
  static ModInt fact(long long n){
    return ModInt::fact(n, default_mod);
  }
  static ModInt comb(long long n, long long r, int mod){
    if(r > n){
      return ModInt(0, mod);
    }
    return ModInt::fact(n) * ModInt::fact(r).inv() * ModInt::fact(n - r).inv();
  }
  static ModInt comb(long long n, long long r){
    return ModInt::comb(n, r, default_mod);
  }
 
  friend ostream& operator<< (ostream& os, const ModInt& modint){
    os << modint.val;
    return os;
  }
  friend istream& operator>>(istream& is, ModInt& modint){
    long long val;
    cin >> val;
    modint.val = val % modint.mod;
  }
private:
  long long val;
  int mod;
};

long long N, M, K;

int main(){
    cin >> N >> M >> K;
    auto ans_x = ModInt(6).inv() * ModInt(M) * ModInt(M) * ModInt::comb(N * M - 2, K - 2) * ModInt(N) * ModInt(N - 1) * ModInt(N + 1);
    auto ans_y = ModInt(6).inv() * ModInt(N) * ModInt(N) * ModInt::comb(N * M - 2, K - 2) * ModInt(M) * ModInt(M - 1) * ModInt(M + 1);

    cout << ans_x + ans_y << endl;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()
A=int(input())
B=int(input())
C=int(input())
X=int(input())
count=0
for a in range(A+1):
    for b in range(B+1):
        rest = X-500*a-100*b
        if rest<0:
            continue
        if rest % 50 == 0 and rest // 50 <= C:
            count+=1
print(count)

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll get2(ll x){
	ll res = 0;
	while(x%2==0){
		res++;
		x/=2;
	}
	return res;
}

int main(){
	ll N;
	cin >> N;
	vector<ll> a(N);
	REP(i, N) cin >> a[i];

	ll res = 0;
	REP(i, N) res += get2(a[i]);

	cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
n = int(input())
w_lst = list(map(int, input().split()))
min = 1000000
for i in range(1, n):
    s1 = sum(w_lst[:i])
    s2 = sum(w_lst[i:])
    if abs(s1 - s2) < min:
        min = abs(s1 - s2)
print(min)

Measured memory_bytes: 3060
import sys
from collections import Counter
h, w = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
ct = Counter()
for y in range(h):
    a = [i for i in sys.stdin.readline().strip()]
    a_ls.append(a)
    ct.update(a)
g1 = h % 2 & w % 2
g2 = (h // 2) * (w % 2) + (w // 2) * (h % 2)
g4 = (h // 2) * (w // 2)
cnt = 0
for c in ct.keys():
    if cnt == g1:
        break
    if ct[c] % 2 == 1:
        ct[c] -= 1
        cnt += 1
cnt = 0
for c in ct.keys():
    if cnt == g2:
        break
    if ct[c] % 4 == 2:
        ct[c] -= 2
        cnt += 1
if all([ct[c] % 4 == 0 for c in ct.keys()]):
    print("Yes")
else:
    print("No")

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

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

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll N;
    cin >> N;
    vector<double> A(N);
    double bunshi = 1.0;
    REP(i, N){
        cin >> A[i];
        bunshi *= A[i];
    }

    double bunbo = 0.0;
    REP(i, N ){
       bunbo += bunshi/A[i];
    }

    cout << bunshi/bunbo << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    sort(a,a+n);
    ll ans=0,sum=0;
    for(int i=n-1;i>=0;i--){
    	if(sum+a[i]<k)sum+=a[i],ans++;
    	else ans=0;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace AGC002
{
    class B
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = input[0];
            int M = input[1];

            //ballの数を持つ配列
            int[] Num = new int[N].Select(x => 1).ToArray();
            //Console.WriteLine(string.Join(",", Num));

            //赤が入っている可能性があるか判断するための配列
            bool[] Red = new bool[N];

            //T -> F へ移動したときに、 F -> T へと変更する(移動時はballの数をマイナスする)
            //最初Tだったとしても、ballの数が0個になった時、T -> F へと変更する
            Red[0] = true;

            for (int i = 0; i < M; i++)
            {
                input = Console.ReadLine().Split().Select(int.Parse).ToArray();
                int x = input[0] - 1;
                int y = input[1] - 1;

                Num[x]--;
                Num[y]++;

                if (Red[x] == true) { Red[y] = true; }
                if (Num[x] == 0) Red[x] = false;
            }

            long sum = Red.Count(x => x == true);

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 19168
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <set>
#include <limits>
#define int long long

using namespace std;

using edge = pair<int, int>;
constexpr int INF = numeric_limits<int>::max() / 2;

vector<int> dijkstra(vector<vector<edge>> const& es, int start) {
    int const N = es.size();
    vector<int> result(N, INF);
    using D = pair<int, int>;
    priority_queue<D, vector<D>, greater<D>> que;
    result[start] = 0;
    que.emplace(0, start);
    while (!que.empty()) {
        int d, v;
        tie(d, v) = que.top();
        que.pop();
        if (result[v] < d) continue;
        for (auto e : es[v]) {
            int cost, to;
            tie(cost, to) = e;
            if (result[v] + cost > result[to]) continue;
            result[to] = result[v] + cost;
            que.emplace(result[to], to);
        }
    }
    return move(result);
}

signed main() {
    int n, m, c;
    cin >> n >> m >> c;
    vector<vector<edge>> es(n);
    int sum_distance = 0;
    for (int i = 0; i < m; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        a--;
        b--;
        es[a].emplace_back(d, b);
        es[b].emplace_back(d, a);
        sum_distance += d;
    }
    vector<int> dist = dijkstra(es, 0);
    vector<pair<int, int>> candidates(n);
    for (int i = 0; i < n; i++)
        candidates[i] = {dist[i], i};
    sort(begin(candidates), end(candidates));
    int minimum = INF,
        fix = sum_distance;
    set<int> near;
    for (auto v : candidates) {
        int x, vertex;
        tie(x, vertex) = v;
        near.insert(vertex);
        for (auto e : es[vertex])
            if (near.count(e.second))
                fix -= e.first;
        int cost = c * x + fix;
        minimum = min(minimum, cost);
    }
    cout << minimum << endl;
}

Measured memory_bytes: 22084
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define dprint(Exp,...) if(Exp){fprintf(stderr, __VA_ARGS__);}
#define printe(...) fprintf(stderr, __VA_ARGS__);
#define PrtExp(_Exp)  cerr<< #_Exp <<" = "<< (_Exp)
#define PrtExpN(_Exp)  cerr<< #_Exp <<" = "<< (_Exp) <<"\n"

#define SINT(n) scanf("%d",&n)
#define SINT2(n,m) scanf("%d %d",&n,&m)
#define SINT3(n,m,o) scanf("%d %d %d",&n,&m,&o)
#define SINT4(n,m,o,p) scanf("%d %d %d %d",&n,&m,&o,&p)
#define SINT5(n,m,o,p,q) scanf("%d %d %d %d %d",&n,&m,&o,&p,&q)
#define SLL(n) scanf("%lld",&n)
#define SLL2(n,m) scanf("%lld %lld",&n,&m)
#define SLL3(n,m,o) scanf("%lld %lld %lld",&n,&m,&o)
#define SST(s) scanf("%s",s)
#define SCH(c) scanf("%c",&c)

#define GC() getchar()

#define PINT(n) printf("%d",(int)(n))
#define PINT2(n,m) printf("%d %d",(int)(n),(int)(m))
#define PINT3(n,m,l) printf("%d %d %d",(int)(n),(int)(m),(int)(l))
#define PLL(n) printf("%lld",(long long)(n))
#define PST(s) printf("%s",(s))
#define PCH(s) printf("%c",(s))

#define PINTN(n) printf("%d\n",(int)(n))
#define PINT2N(n,m) printf("%d %d\n",(int)(n),(int)(m))
#define PINT3N(n,m,l) printf("%d %d %d\n",(int)(n),(int)(m),(int)(l))
#define PLLN(n) printf("%lld\n",(long long)(n))
#define PSTN(s) printf("%s\n",(s))
#define PCHN(s) printf("%c\n",(s))

#define PSP() printf(" ")
#define PN() printf("\n")

#define PC(c) putchar(c)
#define CSP (' ')
#define SN ("\n")

#define rep(i,a) for(int i=0;i<a;i++)
#define reP(i,a) for(int i=0;i<=a;i++)
#define Rep(i,a) for(int i=a-1;i>=0;i--)
#define ReP(i,a) for(int i=a;i>=0;i--)

#define rEp(i,a) for(i=0;i<a;i++)
#define rEP(i,a) for(i=0;i<=a;i++)
#define REp(i,a) for(i=a-1;i>=0;i--)
#define REP(i,a) for(i=a;i>=0;i--)

#define repft(i,a,b) for(int i=a;i<b;i++)
#define repfT(i,a,b) for(int i=a;i<=b;i++)
#define Repft(i,a,b) for(int i=a-1;i>=b;i--)
#define RepfT(i,a,b) for(int i=a;i>=b;i--)

#define foreach(a,it) for(auto it = a.begin(); it != a.end(); ++it)

#define FILL(a,v) fill(begin(a),end(a), v)
#define FILL0(a) memset(a,0,sizeof(a))
#define FILL1(a) memset(a,-1,sizeof(a))

typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll>   Pll;

typedef pair<double, double> Pd;


const int INF = 1000000009; //0x2aaaaaaa; // 715,827,882
const ll INFLL = 0x1f1f1f1f1f1f1f1fLL;//2,242,545,357,980,376,863

template <class A, class B> inline ostream& operator<<(ostream& st, const pair<A, B>& P) { return st << "(" << P.first << ", " << P.second << ")"; };
template <class A, class B> inline pair<A, B> operator+(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first + Q.first, P.second + Q.second); };
template <class A, class B> inline pair<A, B> operator-(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first - Q.first, P.second - Q.second); };

#define fs  first
#define sc  second



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

	int r0 = a * x + b * y;

	int n = min(x, y) * 2;
	int ret = n * c;
	int r1 = ret + a * (x - n / 2) + b * (y - n / 2);

	int r3 = max(x, y) * c * 2;

	cout << min(r0, min(r1, r3)) << endl;


}

Measured memory_bytes: 256
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <iomanip>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){ 
    int n,k; cin>>n>>k;
    ld ans=0.0;
    for (int i=1;i<=n;i++){
        int h=i,p=1;
        while (h<k){
            h*=2; p *= 2;
        }
        ans += (1.0/(p*n)) ; 
    }
    cout.precision(20);
    cout << ans << endl;
} 

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3740
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll Cost;
struct Edge{int to,cap,rev;Cost cost;};
typedef vector<Edge> Edges;
typedef vector<vector<Edge> > Graph;
typedef pair<Cost,int> Que;
 
void add_edge(Graph &g,int from,int to,int cap,Cost cost=0){
  g[from].pb((Edge){to,cap,(int)g[to].size(),cost});
  //  g[to].pb((Edge){from,0,(int)g[from].size()-1,-cost});
}
Cost INF=5e15;
//dij
 
void dij(Graph &g,int s,vector<Cost> &d){
  priority_queue<Que,vector<Que>,greater<Que> > que;
  int V=g.size();
  d.resize(V);
  fill(all(d),INF);
  d[s]=0;
  que.push(Que(0,s));
  while(!que.empty()){
    Que p=que.top();que.pop();
    int v=p.Y;
    if(d[v]<p.X)continue;
    for(int i=0;i<g[v].size();i++){
      Edge e=g[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(Que(d[e.to],e.to));
      }
    }
  }
}
Cost d[25][112][112];

int main(){
  int n,m,c,s,dst;
  while(cin>>n>>m>>c>>s>>dst){
    if(!n)break;
    --s; --dst;
    fill(d[0][0],d[0][0]+25*112*112,INF);
    rep(i,c)rep(j,n)d[i][j][j]=0;
    ll x,y,d_,t;
    rep(i,m){
      cin>>x>>y>>d_>>t;
      --x; --y; --t;
      d[t][x][y]=d[t][y][x]=min(d[t][y][x],d_);
    }
    if(0)rep(i,c){
      rep(j,n){rep(k,n)cout<<d[i][j][k]<<",";cout<<endl;}
      cout<<endl;
    }
    rep(t,c)
      rep(k,n)rep(i,n)rep(j,n)
      d[t][i][j]=min(d[t][i][j],d[t][i][k]+d[t][k][j]);
    if(0)rep(i,c){
      rep(j,n){rep(k,n)cout<<d[i][j][k]<<",";cout<<endl;}
      cout<<endl;
    }
    
    vector<vector<ll>> p(c),r(c),sum(c);
    rep(i,c){
      cin>>t;
      p[i].resize(t); r[i].resize(t); sum[i].resize(t);
    }
    rep(i,c){
      rep(j,p[i].size())if(j)
	cin>>p[i][j];
      rep(j,r[i].size())
	cin>>r[i][j];
      //rep(j,r[i].size())cout<<r[i][j]<<" ";cout<<endl;
      rep(j,r[i].size()-1)
	sum[i][j+1]=sum[i][j]+(p[i][j+1]-p[i][j])*r[i][j];
      //rep(j,r[i].size())cout<<sum[i][j]<<" ";cout<<endl;
    }
    Graph g(n);
    rep(i,c)rep(j,n)rep(k,j){
      //    cout<<d[i][j][k]<<endl;
      if(d[i][j][k]!=INF){
	int t=upper_bound(all(p[i]),d[i][j][k])-p[i].begin()-1;
	ll cost=sum[i][t]+(d[i][j][k]-p[i][t])*r[i][t];
	//cout<<i<<","<<d[i][j][k]<<":"<<cost<<","<<p[i][t]<<","<<r[i][t]<<endl;
	add_edge(g,k,j,0,cost);
	add_edge(g,j,k,0,cost);
      }
    }
    vector<Cost> re;
    dij(g,s,re);
    cout<<(re[dst]==INF?-1:re[dst])<<endl;
  }
}

Measured memory_bytes: 8704
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
  int N, T;
  cin >> N >> T;
  int c[N], t[N];
  int cost = 10000;
  int index = -1;
  for(int i=0; i < N; ++i){
    cin >> c[i] >> t[i];
    if(t[i] <= T){
      if(c[i] < cost){
        cost = c[i];
        index = i;
      }
    }
  }

  if(index == -1){
    cout << "TLE" << endl;
  }else{
    cout << c[index] << endl;
  }


  return 0;
}


Measured memory_bytes: 256