akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 2e5+5;
set<pair<int,int>> s1;
vector<pair<int,pair<int,int>>> v1;
int ans[MAXN];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        v1.push_back(make_pair(z,make_pair(x-z,y-z-1)));
    }
    sort(v1.begin(),v1.end());
    for(int i=0;i<k;i++){
        int a;
        cin>>a;
        s1.insert(make_pair(a,i));
    }
    for(int i=0;i<n;i++){
        int l = v1[i].second.first;
        int r = v1[i].second.second;
        int x = v1[i].first;
        
        while(!s1.empty()){
            auto it = s1.lower_bound(make_pair(l,-1));
            if(it == s1.end()){
                break;
                
            }
            auto p = *it;
            //cout<<p.first<<" "<<l<<" "<<r<<" "<<x<<endl;
            if(p.first > r){
                break;
            }
            ans[p.second] = x;
            s1.erase(p);
        }
        
    }
    while(!s1.empty()){
        auto it =s1.begin();
        s1.erase(*it);
        ans[(*it).second] = -1;
    }
    for(int i=0;i<k;i++){
        cout<<ans[i]<<endl;
    }
}

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

int main()
{
 int A,B,C,D;
  cin >> A >> B >> C >> D;
  while(1)
  {
   C=C-B;
   if(C<=0) break;
   A=A-D;
   if(A<=0) break;
  }
  
  if(A<=0)
  {
  cout<<"No"<<endl;
  return 0;
  }
  if(C<=0)
  {
  cout<<"Yes"<<endl;
  return 0;
  }
  
}


Measured memory_bytes: 3652
if __name__ == '__main__':
    N = int(input())

    SP_list = [[i+1] + list(input().split()) for i in range(N)]

    SP_list = [[int(sp[0]), str(sp[1]), int(sp[2])] for sp in SP_list]

    for sp in sorted(SP_list, key=lambda x:(x[1], -x[2])):
        print(sp[0])


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

int N;

int main(){
cin>>N;

int A[N];

for(int i=0;i<N;i++)cin>>A[i];
sort(A,A+N,greater<int>());
int Alice=0;
int Bob=0;
for(int i=0;i<N;i++){
    Alice += A[i];
    if(i==N-1) break;
    i++;
    Bob += A[i];
}
cout<<Alice-Bob<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

struct UnionFind{
    vector<ll> par;
    vector<ll> sizes;
    UnionFind(ll n) : par(n), sizes(n, 1) {
        rep(i,n) par[i] = i;
    }
    int find(ll x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
    }

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

    ll size(ll x) {
        return sizes[find(x)];
    }
};


int main(){
    int n, m;
    cin >> n >> m;
    UnionFind tree(n);

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        tree.unite(a,b);
    }
    ll ans = 0;
    rep(i, n){
        ans = max(ans, tree.size(i));
    }

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


Measured memory_bytes: 6416
#include<stdio.h>
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	if((a+b)%3==0||a%3==0||b%3==0)
	{
		printf("Possible\n");
	}
	else
	{
		printf("Impossible\n");
	}
}

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

const string YES = "YES";
const string NO = "NO";

void solve(std::string S)
{
    array<string, 4> words = { "dream", "dreamer", "erase", "eraser" };
    while (!S.empty()) {
        bool found = false;
        for (auto&& word : words) {
            auto find_pos = S.rfind(word);
            if (find_pos != string::npos && find_pos == S.size() - word.size()) {
                found = true;
                S.resize(find_pos);
                break;
            }
        }
        if (!found) {
            cout << NO << endl;
            return;
        }
    }

    cout << YES << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
int main(){
    std::string S;
    std::cin >> S;
    cin.tie(nullptr);
    cout.tie(nullptr);
	ios_base::sync_with_stdio(false);
    solve(S);
    return 0;
}


Measured memory_bytes: 512
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iterator>
#include <sstream>

using namespace std;

int main()
{
	int n;
	while(cin>>n,n){
		int ans = 0;
		for (int i = n / 5; i > 0; i /= 5){
			ans += i;
		}
		cout << ans <<endl;
	}
	return 0;
}

Measured memory_bytes: 0
open System

let n, m, q =
    let l = Console.ReadLine().Split(' ') |> Array.map int
    l.[0], l.[1], l.[2]

let abcd =
    [ 1 .. q ]
    |> List.map (fun _ ->
        let l = Console.ReadLine().Split(' ') |> Array.map int
        l.[0], l.[1], l.[2], l.[3])

let total (arr: int List) =
    [ 0 .. q - 1 ]
    |> List.map (fun i ->
        let a, b, c, d = abcd.[i]
        if arr.[b - 1] - arr.[a - 1] = c then d else 0)
    |> List.sum

let ans =
    let rec dfs (l: int List) =
        if l.Length = n then
            total l
        else
            let len = l.Length

            let h =
                if len = 0 then 1 else l.[len - 1]
            [ h .. m ]
            |> List.map (fun i -> dfs (l @ [ i ]))
            |> List.max
    dfs []

ans |> printfn "%d"


Measured memory_bytes: 43136
#include <stdio.h>


// ?????\???????§???????
typedef struct {
    char name[11];
    int time;
} Queue;


int main()
{
    //??\???
    int n, q;
    scanf("%d%d", &n, &q);

    int size = 2 * n; //?????\???????????????
    Queue Queue[size];
    int pre = 0, rear = 0, cnt = 0; //pre:enqueue, rear:inqueue, cnt:????????????
    for( rear = 0; rear < n; ++rear )
        scanf("%s %d", Queue[rear].name, &Queue[rear].time);


    //????????¨??????
    while( pre != rear ){
        if( Queue[pre].time <= q ){ // if( Queue[pre].time == q ){ inqueue????????? }
            cnt += Queue[pre].time;
            printf("%s %d\n", Queue[pre].name, cnt);
        } else {
            cnt += q;
            Queue[pre].time -= q;
            Queue[rear] = Queue[pre]; //inqueue
            rear = (rear + 1) % size; //?¬????inqueue???
        }

        //?¬????dequeue???
        pre = (pre + 1) % size;
    }


    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e16+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

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

    string s;
    cin>>s;
    ll n = s.size();

    ll ans=INF;

    rep(i,n-2){
        string tmp = {s[i],s[i+1],s[i+2]};
        ll x = stoi(tmp);
        ans = min(ans,abs(x-753));
    }


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


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

int main(){
    int n;
    cin >> n;
    map<string,int> m;
    rep(i,n){
        string s;
        cin >> s;
        m[s]++;
    }
    vector<vector<string>> ans(200005);
    int mi = 0;
    for(auto p : m){
        mi = max(mi, p.second);
        ans[p.second].push_back(p.first);
    }
    sort(ans[mi].begin(), ans[mi].end());
    for(auto p : ans[mi]) cout << p << endl;
}

Measured memory_bytes: 31908
#include <bits/stdc++.h>
#include <cstdlib>  // abs() for integer 絶対値求めやつ
#include <cmath>    // abs() for float, and fabs()
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i = 0; i < (n);i++)
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
using namespace std;
#define INF 2000000000
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
string s;
int main(){
	cin>>s;
	int n = s.size();
	int ans = 0;
	for(int i = 0; 2*(i+1)< n; i++){
		int k = i+1;
	string a =s.substr(0,k);
	string b =s.substr(k,k);
	if(a==b){
		ans = max(ans,k*2);
	}
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 256
N = int(input())
a =  list(map(int,input().split()))
b = [0, abs(a[1]-a[0])]


for i in range(2,N):
   b.append(min(b[i-2]+abs(a[i]-a[i-2]),b[i-1]+abs(a[i]-a[i-1])))
    

print(b[-1])

Measured memory_bytes: 55144
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<typeinfo>

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

int main(){
  ll n;cin>>n;
  cout<<(n/11)*2+ll(n%11>0)+ll(n%11>6)<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define INF 1000000
#define MAX_V 110
using namespace std;

int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;
int e[MAX_V][MAX_V];

void dijkstra(int s){
	int u;
	fill (d,d+V,INF);
	fill (used,used+V,false);
	d[s] = 0;
	while(true){
		int v = -1;
		for(u=0;u<V;u++){
			if(used[u]!=true && (v==-1 || d[u]<d[v])){
				v = u;
			}
		}
		if(v==-1){
			break;
		}
			
		used[v] = true;
			
		for(u=0;u<V;u++){
			d[u] = min(d[u],d[v]+cost[v][u]);
		}
	}
	for(u=0;u<V;u++){
		e[s][u] = d[u];
	}
}

int main(){
	int ans,i,j,k,M;
	cin >> V >> M ;
	int a[M],b[M],c[M];
	ans = M;
		for(i=0;i<V;i++){
			for(j=0;j<V;j++){
				cost[i][j] = INF;
			}
		}
	
	for(int i=0;i<M;i++){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;
		b[i]--;
		cost[a[i]][b[i]] = c[i];
		cost[b[i]][a[i]] = c[i];
	}

	for(i=0;i<V;i++){
		dijkstra(i);
	}
	
	for(k=0;k<M;k++){
		for(i=0;i<V;i++){
			if(e[i][a[k]] + cost[a[k]][b[k]] == e[i][b[k]]){
				ans -= 1;
				break;
				}
		}
	}
	cout << ans << endl;		
}




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

n = int(input())
nums = [int(x) for x in input().split()]
count = -1
flag = 0
while(True):
    count += 1
    for i in range(n):
        if nums[i] % 2 == 0:
            nums[i] = nums[i] / 2
            #print(nums[i])
        else:
            flag = 1
    if flag == 1:
        break
print(count)

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

using namespace std;

#define int long long
#define vi vector <int>
#define all(v) v.begin(), v.end()
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define forn(i, from, n) for (int i = (int)(from); i < (int)(n); ++i)

const int INF = 1e9 + 9;
const int MAXC = 1e5 + 1;

void updMx(int &a, int b){
    if (a < b) a = b;
}

void updMi(int &a, int b){
    if (a > b) a = b;
}

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

#ifdef LOCAL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    int n, W;
    cin >> n >> W;
    vi wei(n + 1), cost(n + 1);
    forn(i, 1, n + 1)
        cin >> wei[i] >> cost[i];
    vector <vi> dp(n + 1, vi(MAXC, INF));
    dp[0][0] = 0;
    forn(i, 1, n + 1){
        forn(c, 0, MAXC)
            dp[i][c] = dp[i - 1][c];
        forn(c, cost[i], MAXC){
            dp[i][c] = dp[i - 1][c];
            updMi(dp[i][c], dp[i - 1][c - cost[i]] + wei[i]);
        }
    }
    int ans = 0;
    forn(i, 0, n + 1)
        forn(c, 0, MAXC)
            if (dp[i][c] <= W)
                updMx(ans, c);
    cout << ans;
    return 0;
}

Measured memory_bytes: 80256
def solve():
    N = raw_input()
    K = int(raw_input())
    L = len(N)
    # digN = []
    # rem = N
    # while (rem != 0):
    #     digN.append(rem%10)
    #     rem = rem / 10
    digN = [int(d) for d in N]
    dp0 = [[1 for i in range(K+1)] for i in range(L)]
    dp1 = [[1 for i in range(K+1)] for i in range(L)]
    dp0[0][0] = 1
    dp1[0][0] = 1
    dp0[0][1] = digN[L-1]
    dp1[0][1] = 9
    for i in range(2, K+1):
        dp0[0][i] = 0
        dp1[0][i] = 0
    for i in range(1, L):
        for j in range(1, K+1):
            if digN[L - 1 - i] > 0:
                dp0[i][j] = (digN[L - 1 - i] - 1) * dp1[i-1][j-1] + dp0[i-1][j-1] + dp1[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j]
            dp1[i][j] = 9 * dp1[i-1][j-1] + dp1[i-1][j]
    print dp0[L-1][K]

if __name__ == '__main__':
    solve()


Measured memory_bytes: 28652
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.next());
        String s = sc.next();
        if (s.length() <= k) {
            System.out.println(s);
        } else {
            System.out.println(s.substring(0, k) + "...");
        }
        sc.close();
    }

}


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

#define INF 1e9 + 5

// for using in pairs
#define F first
#define S second

// aliases
using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ld = long double;

ll gcd(ll a, ll b)
{
	if (!b)
		return a;
	return gcd(b, a % b);
}

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

void solve(int tc)
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll L = lcm(c, d);

	a--;

	ll A = b - b / c - b / d + b / L;
	ll B = a - a / c - a / d + a / L;

	cout << A - B << "\n"; 

}

int32_t main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	// cin >> t;

	for (int i = 1; i <= t; i++)
	{
		solve(i);
	}
	return 0;
}


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

int32_t main()
{

   int k; cin>>k;
   int ans = 0;
   for(int i=1;i<=k;i++)
   {

       for(int j=1;j<=k;j++)
       {

           for(int l=1;l<=k;l++)
           {
               ans= ans + __gcd(i,__gcd(j,l));
           }
       }
   }
   cout<<ans;
}


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

using namespace std;

int N, M, K;
int A[200005], B[200005];
int ans;

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);
	for (int i = 0; i < M; i++) scanf("%d", &B[i]);
	int ai = 0, bi = 0, curk = 0, curans = 0;
	while (curk + A[ai] <= K && ai < N) {
		curans++;
		curk += A[ai++];
		ans = max(ans, curans);
	}
    while (curk + B[bi] <= K && bi < M) {
        curans++;
        curk += B[bi++];
        ans = max(ans, curans);
    }
	for (int i = ai - 1; i >= 0; i--) {
		curans--;
		curk -= A[i];
		while (curk + B[bi] <= K && bi < M) {
			curans++;
			curk += B[bi++];
			ans = max(ans, curans);
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 5272
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

bool even(string& s) {
  if (s.size() % 2 == 1) return false;
  int n = s.size() / 2;
  for (int i = 0; i < n; i++) {
    if (s[i] != s[i+n]) return false;
  }
  return true;
}

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

  string s;
  cin >> s;

  s.erase(s.end() - 1);

  while (!even(s)) {
    s.erase(s.end() - 1);
  }

  cout << s.size() << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;
int main() {
string S;
cin >> S;
int N = S.size();
bool ans = true;
for (int i = 0; i < N/2; i++) {
    if (S.at(i) != S.at(N -i-1)) {
        ans = false;
        break;
    } 
    
}
for (int i = 0;i < (N-1)/ 2 - 1;i++) {
    if (S.at(i) != S.at(N/2 -i-1)) {
    
        ans = false;
        break;
    }
}
for (int i = (N+3)/2;i < N;i++) {
    if (S.at(i) != S.at(N-1-i)) {
        ans = false;
        break;
    }
}

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

return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(void){

    int A,B;
    cin>>A>>B;
    if(A+B>=A-B){
        if(A+B>=A*B){
            cout<<A+B<<endl;
        }else{
            cout<<A*B<<endl;
        }
    }else{
        if(A-B>=A*B){
            cout<<A-B<<endl;
        }else{
            cout<<A*B<<endl;
        }

    }


    return 0;
}

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

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int>> p(N, vector<int>(D));
  for(int i=0; i<N; i++){
    for(int j=0; j<D; j++) cin >> p.at(i).at(j);
  }
  
  double tmp;
  int itmp,cnt=0;
  
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      tmp = 0.0;
      for(int k=0; k<D; k++) tmp += (double)(p.at(i).at(k)-p.at(j).at(k))*(p.at(i).at(k)-p.at(j).at(k));
      tmp = sqrt(tmp);
      itmp = (int)tmp;
      tmp = tmp - (double)itmp;
      if(tmp == 0) cnt++;
    }
  }

  
  cout << cnt << endl;
}


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

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i,begin,end) for(int i=begin; i>end; i--)
#define lld long long int

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    printf(n==m? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 13;
const int M = 1e3 + 7;
const int INF = 1e9 + 239;

int dp[M][(1 << N)];

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

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << N); j++) {
			dp[i][j] = INF;
		}
	}

	int n, m;
	cin >> n >> m;
	dp[0][0] = 0;
	for (int i = 0; i < m; i++) {
		int cost, sz;
		cin >> cost >> sz;
		int c = 0;
		while (sz--) {
			int x;
			cin >> x;
			x--;
			c |= (1 << x);
		}
		for (int wm = 0; wm < (1 << n); wm++) {
			dp[i + 1][wm] = min(dp[i + 1][wm], dp[i][wm]);
			dp[i + 1][wm | c] = min(dp[i + 1][wm | c], dp[i][wm] + cost);
		}
	}
	int ans = dp[m][(1 << n) - 1];
	if (ans == INF) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
}


Measured memory_bytes: 32640
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define pb push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr double eps = 1e-14; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

constexpr ll MN = 100011;
ll N;

array<ll,MN> A;
array<vector<ll>,MN> g;
bool ans=true;

ll dfs(ll c,ll p){
    if(!ans) return -1;
    // leaf
    if(sz(g[c])==1) return A[c];
    // not leaf
    vector<ll> ch;
    for(auto v:g[c]) if(v!=p){
        ch.pb(dfs(v,c));
    }
    ll mx = *max_element(all(ch));
    ll sum = accumulate(all(ch),0);

    ll np = 2*A[c]-sum; // connect for the direction of parent
    ll cp = (sum-np)/2; // need pair of child and child

    if(np<0 or (sum-np)%2==1 or np>sum){ ans=false; }
    if(sum-mx<cp){ ans=false; }
    //cout << "dfs(" << c << "," << p << ") = " << np << ", cp=" << cp << endl;
    return np;
}

int main(){
    cin >> N;
    rep(i,N) cin>>A[i];
    rep(i,N-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }

    if(N==2){
        cout << (A[0]==A[1] ? "YES" : "NO") << endl;
        return 0;
    }

    ll tmp;
    for(int i=0;i<N;i++) if(sz(g[i])>1){
        //cout << "root:" << i << endl;
        tmp = dfs(i,-1);
        break;
    }
    if(!ans){
        cout << "NO" << endl;
        return 0;
    }
    if(tmp==0) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 14464
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<complex>
#include<algorithm>
#include<vector>
#include<math.h>
#include<set>
#include<map>

int main()
{
	int n;
	scanf("%d", &n);
	if (n / 100 == n % 10)
		printf("Yes\n");
	else
		printf("No\n");
	
	return 0;
}

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

int main(void){
	string s;
	vector<int>x, y;
	int x_ans, y_ans;
	cin >> s >> x_ans >> y_ans;
	int cnt = 0;
	bool mode = true;
	for(int i = 0; i < s.size();i++){
		if(s[i] == 'T'){
			if(cnt != 0){
				if(mode){
					x.push_back(cnt);
				}else{
					y.push_back(cnt);
				}
			}
			mode = !mode;
			cnt = 0;
		}else{
			cnt++;
		}
	}
	if(cnt != 0){
		if(mode){
			x.push_back(cnt);
		}else{
			y.push_back(cnt);
		}
	}
	int fx = 0;
	if(s[0] == 'F'){
		fx = x[0];
		x[0] = 0;
	}
	bool dp[8010][16010]; // 8000 + num, 8000 - num
	for(int i = 0; i < 8010; i++){
		for(int j = 0; j < 16010; j++){
			dp[i][j] = false;
		}
	}
	dp[0][8000] = true;
	for(int i = 0; i < x.size(); i++){
		for(int j = 0; j < 16010; j++){
			if(j + x[i] >= 0){
				dp[i+1][j] |= dp[i][j+x[i]];
			}
			if(j - x[i] >= 0){
				dp[i+1][j] |= dp[i][j-x[i]];
			}
		}
	}
	if(!dp[x.size()][8000+x_ans-fx]){
		cout << "No" << endl;
		return 0;
	}

	for(int i = 0; i < 8010; i++){
		for(int j = 0; j < 16010; j++){
			dp[i][j] = false;
		}
	}
	dp[0][8000] = true;
	for(int i = 0; i < y.size(); i++){
		for(int j = 0; j < 16010; j++){
			if(j + y[i] >= 0){
				dp[i+1][j] |= dp[i][j+y[i]];
			}
			if(j - y[i] >= 0){
				dp[i+1][j] |= dp[i][j-y[i]];
			}
		}
	}
	if(!dp[y.size()][8000+y_ans]){
		cout << "No" << endl;
		return 0;
	}

	cout << "Yes" << endl;
	return 0;
}

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


int main()
{
    int t;
    cin>>t;
    int n=t%10;
    if(n==2 || n==4 || n==5 || n==7 || n==9 )
        cout<<"hon"<<endl;
    else if(n==0 || n==1 || n==6 || n==8 ) 
        cout<<"pon"<<endl;
    else if(n==3)
    {
        cout<<"bon"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3632
N,M = map(int,input().split())
Xs = list(map(int,input().split()))
Xs.sort()
diffs = []
for i in range(1,M):
    diffs.append(Xs[i]-Xs[i-1])
if len(diffs) > 0 and M > N:
    diffs.sort()
    print(sum(diffs[:M-N]))
else:
    print(0)

Measured memory_bytes: 13960
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
ans=1
v=True
for i in arr:
    ans=ans*i
    if ans==0:
        v=False
        print(0)
        break
        
    if ans>1000000000000000000:
        v=False
        print(-1)
        break

if v:
    print(ans)
    


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

int main() {
  vector<bool> seen(26, false);
  char c;
  bool flag = true;
  while (cin >> c) {
    if (seen[c-'a']) flag = false;
    seen[c-'a'] = true;
  }
  cout << (flag ? "yes" : "no") << endl;
  return 0;
}

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

typedef long long ll;
const int MOD = 1000000007;

ll mod_pow(ll a, ll b) {
    if (b == 0) return 1;
    ll res = mod_pow(a * a % MOD, b / 2);
    if (b % 2 == 1) res = res * a % MOD;
    return res;
}

ll comb(ll a, ll b) {
    ll res = 1;
    for (int i = 0; i < b; i++) {
        res = res * (a - i) % MOD * mod_pow(i + 1, MOD - 2) % MOD;
    }
    return res;
}

int main() {
    ll X, Y;
    cin >> X >> Y;

    ll res = 0;
    for (ll n = 0; n < X + 1; n++) {
        if ((X - n) % 2 != 0) continue;
        if ((Y - 2 * n) != ((X - n) / 2)) continue;

        ll m = Y - 2 * n;
        res += comb(n + m, n);
    }

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

Measured memory_bytes: 256
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


# 個数制限付きナップザック問題
def main():
    H, N = MI()
    A = [0] * N
    B = [0] * N
    dp = [IINF] * (H+1)
    dp[0] = 0

    for i in range(N):
        A[i], B[i] = MI()

    for i in range(N):
        dp_next = [IINF] * (H+1)
        for j in range(H+1):
            dp_next[j] = min(dp_next[j], dp[j])
            if j + A[i] <= H:
                # print(j, dp_next[j + A[i]], dp[j + A[i]], dp[j] + B[i], dp_next[j] + B[i])
                dp_next[j + A[i]] = min(dp_next[j + A[i]], dp[j + A[i]], dp_next[j] + B[i])
            else:
                # print(j, dp_next[H], dp[H], dp[j] + B[i], dp_next[j] + B[i])
                dp_next[H] = min(dp_next[H], dp[H], dp_next[j] + B[i])
        dp = dp_next
        # print(dp_next)
    print(dp[H])



if __name__ == '__main__':
    main()


Measured memory_bytes: 45016
#include<bits/stdc++.h>
#define int long long int
#define ld long double
#define getFaster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define rev(i,n,init) for(int i=n;i>=init;i--)
#define MAXN 200005
#define MOD2 998244353
#define MOD1 1e9+7
#define f first
#define s second
#define ylol1 y1
#define endl '\n'
#define pii pair<int,int>
#define piii pair<pii,int>
#define precise(i) cout<<fixed<<setprecision(i)
#define codejam cout<<"Case #"<<ii+1<<": ";
#define impossible cout<<"IMPOSSIBLE"<<endl;
#define error(s) throw runtime_error(s)
using namespace std;
const long double PI = atan(1.0)*4;
const int64_t INF=1e14;
const int32_t LOG=21;
const int MOD=MOD2;

int power(int x,int y)
{
    if(y==0)return 1;
    int temp=power(x,y/2);
    temp=(temp*temp)%MOD;
    if(y&1)temp=(temp*x)%MOD;
    return temp;
}

int fact[200005];
int inv[200005];

void init()
{
	fact[0]=inv[0]=1;
	rep(i,1,200001)
	{
		fact[i]=(i*fact[i-1])%MOD;
		inv[i]=power(fact[i],MOD-2);
	}
}

int ncr(int n,int r)
{
	  if(n<r)return 0;
	  int x=(fact[n]*inv[r])%MOD;
	  x=(x*inv[n-r])%MOD;
	  return x;
}

int32_t main()
{ 
      getFaster;
      int tests=1;
      //cin>>tests;
      rep(ii,0,tests)
      {
      	    init();
            int n,m,k;
            cin>>n>>m>>k;
            int ans=0;
            rep(i,n-k,n+1)
            {
            	int temp=(m*power(m-1,i-1))%MOD;
            	temp=(temp*ncr(n-1,i-1))%MOD;
                ans+=temp;
                while(ans>=MOD)ans-=MOD;
            }
            cout<<ans<<endl; 
      }
      return 0;                         
}

/*
 TIPS:
 1.) Check for corner cases (like 0 is exception case)
 2.) Check for global memory sizes,memory refreshments and its complexity 
 3.) Check for sorting criteria (if used 1-based indexing)
 4.) Check for numbers overflow (while multiplying and doing MOD)
 5.) Check for typecasting issues like int to float( while dividing numbers)
*/

Measured memory_bytes: 6780
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

W, H, x,y =[int(x) for x in input().split()]

print ((W*H)/2)
if x == W/2 and y == H/2:
    print(1)
elif W == 0 or H == 0:
    print(0)
else:
    print(0)




Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    int A, B, C;
    int ans;

    //input
    cin >> A >> B >> C;

    ans = C - (A - B);
    if(ans < 0){
        ans = 0;
    }

    //output
    cout << ans << endl;

    return 0;
}


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

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

    for(int i = 1; i < 10; i++){
        for(int j = 1; j < 10;j++){
            if(i * j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

using namespace std;

int main() {

	set<string> mySet;
	string temp;
	int num;

	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> temp;
		mySet.insert(temp);
	}
	cout << mySet.size() << endl;

	//system("PAUSE");
	return 0;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n, m) for (int (i) = (n); (i) < (m); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

ll C[51][51];

void comb(ll n) {
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= i; j++) {
         if (i == 0 || i == j) {
            C[i][j] = 1;
         } else {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
         }
      }
   }
}

int main() {
   ll n, a, b;
   cin >> n >> a >> b;
   vec<ll> v(n);
   rep (i, 0, n) {
      cin >> v[i];
   }

   comb(n);
   sort(all(v), greater<ll>());

   double maxAvg = 0;
   rep (i, 0, a) {
      maxAvg += v[i];
   }
   maxAvg /= a;

   int num = 0, pos = 0;
   rep (i, 0, n) {
      if (v[i] == v[a-1]) {
         num++;
         if (i < a) pos++;
      }
   }

   ll cnt = 0;
   if (pos == a) {
      for (int i = a; i <= b; i++) {
         cnt += C[num][i];
      }
   } else {
      cnt += C[num][pos];
   }

   printf("%.10f\n", maxAvg);
   printf("%lld\n", cnt);

   return 0;
}

Measured memory_bytes: 256
// Problem : B - Multiple of 9
// Contest : AtCoder - AtCoder Beginner Contest 176
// URL : https://atcoder.jp/contests/abc176/tasks/abc176_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define vi vector<ll>
#define vb vector<bool>
#define vp vector<pair<ll,ll>>
#define mod 1000000007
#define M_PI 3.14159265358979323846
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,b,a) for(ll i=b; i>=a ;--i)
#define vin(a) for(auto &i:a) cin>>i
#define mms(a,n) memset(a,n,sizeof(a))
#define fill(a,value) fill(a.begin(),a.end(),value)
#define all(a) a.begin(),a.end()
#define n_ones(x) __builtin_popcountll(x)
#define n_trailzero(x) __builtin_ctzll(x)
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define see(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it){}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
template <typename T, typename U>inline void min_self(T &x, U y){if (y < x)x = y;}
template <typename T, typename U>inline void max_self(T &x, U y){if (x < y)x = y;}
template<class T1, class T2>ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<"["<<v.first<<", "<<v.second<<"]"; return out<<")"; }
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}

// cout << fixed << setprecision(10) << pi <<" "<<npi<<endl; 
// INT64_MAX
// transform(all(s), s.begin(), ::tolower);

ll XX[4] = {-1,0,1,0};
ll YY[4] = {0,-1,0,1};


void solve(){
    string s;
    cin>>s;
    ll res = 0;
    for(char c:s){
    	res += (c-'0');
    	res %=9;
    }
    
    if(res==0){
    	cout<<"Yes\n";
    }
    else cout<<"No\n";
    
	return;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,k,a[N][N];
int main(){
	scanf("%d",&k),n=(k+1)>>1;
	if(k==1){
		puts("1"),puts("1");
		return 0;
	}
	if(n&1)	++n;
	for(int i=0;i<n;i++)
		for(int j=0,k=i;j<n;j++,k=(k+1)%n)
			a[j][k]=i;
	k-=n;
	for(int i=0;i<k;i++)
		for(int j=0,k=i;j<n;j+=2,k=(k+2)%n)
			a[j][k]=i+n;
	printf("%d\n",n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			printf("%d ",a[i][j]+1);
		putchar('\n');
	}
	return 0;
}


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

using namespace std;

int main(){
    int n,sum = 0;
    string s = "Yes";
    cin >> n;
    vector<int>v(n);

    for(int i = 0;i < n;i++)
        cin >> v[i];

    for(int i = n-1;i >= 1;i--){
        if(v[i] < v[i-1]-1){
            s = "No";
        }else if(v[i] == v[i-1]){
        }else if(v[i] <= v[i-1]-1){
            v[i-1] -= 1;
        }
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 768
import sys

n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
max_val=max(a)

done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

for i in a:
  if done[i-1]==1:
      ans+=1

print(ans)

Measured memory_bytes: 32136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vec<int> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
        A[i]--;
    }
    int id = 0;
    bool ok = false;
    for(int i=0;i<N;i++){
        if(A[i]==id){
            id++;
            ok = true;
        }
    }
    cout << (ok? N-id:-1) << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#include<deque>
#define rep(i,rept)	for(int i = 0; i<(ll)rept;++i)
typedef long long ll;
using namespace std;


int main() {

	int n = 0, t = 0;
	int c = 0, time = 0;
	int ans = 99999999;
	cin >> n >> t;

	rep(i, n) {
		cin >> c >> time;
		if (time <= t) {
			ans = std::min(ans, c);
		}
	}

	if (ans == 99999999) {
		cout << "TLE" << endl;
		return 0;

	}

	cout << ans << endl;


}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

struct P {
  int to, money, cost;
  P(){}
  P(int to, int money, int cost): to(to), money(money), cost(cost) {}

  bool operator < (const P &a) const {
    return cost > a.cost;
  }
};

signed main() {
  int N, M, S;
  cin >> N >> M >> S;

  vector<vector<P>> graph(N);
  REP(i, M){
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    graph[u].emplace_back(v, a, b);
    graph[v].emplace_back(u, a, b);
  }

  vector<int> C(N), D(N);
  REP(i, N) cin >> C[i] >> D[i];

  int MAX_S = 2500;
  S = min(S, MAX_S);

  // dp[i][j]: 都市iまで銀貨j枚残して行く時の最小時間
  vector<vector<int>> dp(N, vector<int>(MAX_S+1, INF));
  dp[0][S] = 0;

  priority_queue<P> q;
  q.emplace(0, S, 0);

  while(!q.empty()){
    auto [v, s, time] = q.top(); q.pop();
    if(time > dp[v][s]) continue;
    
    if(s+C[v] <= MAX_S){
      if(chmin(dp[v][s+C[v]], time+D[v])){
        q.emplace(v, s+C[v], time+D[v]);
      }
    }

    for(auto e : graph[v]){
      int u = e.to;
      int ns = s-e.money;
      int ntime = time+e.cost;

      if(ns >= 0 && chmin(dp[u][ns], ntime)){
        q.emplace(u, ns, ntime);
      }
    }
  }

  FOR(i, 1, N){
    int ret = INF;
    REP(j, MAX_S) chmin(ret, dp[i][j]);
    cout << ret << "\n";
  }

  return 0;
}

Measured memory_bytes: 7304
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
//typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){int i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s,t;
  cin>>s>>t;
  ll A,B;
  cin>>A>>B;
  string u;
  cin>>u;
  if(s==u){A--;}
  else{B--;}
  cout<<A<<" "<<B<<endl;

  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)

def main():
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)

    def lcd(a, b):
        return int(a / gcd(a, b)) * b
    
    a, b = map(int, input().split())
    ans = lcd(a, b)
    print(ans)

if __name__ == '__main__':
    main()

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

const int INF = 1 << 30;

pair<int, vector<int> > solve(int v, vector<vector<int> >& visited, const vector<vector<int> >& path)
{
  pair<int, vector<int> > res = make_pair(0, vector<int>(1, v+1));
  for (int i = 0; i < path[v].size(); ++i) {
    if (!visited[min(v, i)][max(v, i)] && path[v][i] != INF) {
      visited[min(v, i)][max(v, i)] = 1;
      pair<int, vector<int> > tmp = solve(i, visited, path);
      tmp.first += path[v][i];
      tmp.second.push_back(v+1);
      if (tmp.first > res.first)
	res = tmp;
      visited[min(v, i)][max(v, i)] = 0;
    }
  }
  return res;
}

int main()
{
  int ns, nl;
  while (cin >> ns >> nl) {
    if ((ns|nl) == 0)
      break;

    vector<vector<int> > path(ns+1, vector<int>(ns+1, INF));
    for (int i = 0; i < nl; ++i) {
      int s1, s2, d;
      cin >> s1 >> s2 >> d;
      path[s1-1][s2-1] = path[s2-1][s1-1] = d;
    }

    for (int i = 0; i < ns; ++i)
      path[ns][i] = 0;

    vector<vector<int> > visited(ns+1, vector<int>(ns+1, 0));
    pair<int, vector<int> > ans = solve(ns, visited, path);
    cout << ans.first << endl;
    reverse(ans.second.begin(), ans.second.end());
    for (int i = 1; i < ans.second.size()-1; ++i)
      cout << ans.second[i] << " ";
    cout << ans.second.back() << endl;
  }
  return 0;
}

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

ans = 0
for i in range(n):
    left = min(a[i],b[i])
    ans+=left
    a[i]-=left
    b[i]-=left

    right = min(a[i+1],b[i])
    ans+=right
    a[i+1]-=right
    b[i]-=right

print(ans)

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

struct RLAQ{
  int sst[1<<18];
  int adt[1<<18];
  RLAQ(){
    fill(sst,sst+(1<<18),0);
    fill(adt,adt+(1<<18),0);
  }
  void add(int p, int q, int x, int k=0, int l=0, int r=(1<<17)){
    if(r <= p || q <= l) return;
    if(p <= l && r <= q){
      adt[k] += x;
      return;
    }
    add(p, q, x, 2*k+1, l, (l+r)/2);
    add(p, q, x, 2*k+2, (l+r)/2, r);
    sst[k]=min(sst[2*k+1]+adt[2*k+1],sst[2*k+2]+adt[2*k+2]);
  }
  int find(int p, int q, int k=0, int l=0, int r=(1<<17)){
    if(r <= p || q <= l) return INT_MAX;
    if(p <= l && r <= q) return sst[k]+adt[k];
    int m1, m2;
    m1 = find(p,q,2*k+1,l,(l+r)/2);
    m2 = find(p,q,2*k+2,(l+r)/2,r);
    return min(m1,m2)+adt[k];
  }
};

int main(){
  RLAQ a;
  int c,x,y,n,q;
  cin>>n>>q;
  for(int i=0;i<q;i++){
    cin>>c;
    if(!c){
      cin>>x>>y>>c;
      a.add(x,y+1,c);
    }
    else{
      cin>>x>>y;
      cout<<a.find(x,y+1)<<endl;
    }
  }
}


Measured memory_bytes: 5180
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int  a,b,c; cin >> a >> b >> c;
    cout << max(10*a+b+c,max(a+10*b+c,a+b+10*c)) <<endl; return 0;
}


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

typedef long long ll;
typedef struct pair<int,int> P;
int p[1001]={};
int x[1001]={};
int y[1001]={};

int dp[9][(1<<8)]={};
vector<int> v;
int n,m,s;
int d[201][201];
int r[201]={};


//int calc(int s1,int d1){
//	if(dp[s1][d1]>0)return dp[s1][d1];
//	if(d1==(1<<s1))return 0;
//	int d2=d1-(1<<s1);
//	dp[s1][d1]=200000001;
//	for(int i=0;i<s;++i){
//		int k=(1<<i);
//		if((d2&k)==k)dp[s1][d1]=min(dp[s1][d1],d[r[s1]][r[i]]+calc(i,d2));
//	}
//	return dp[s1][d1];
//}
int main() {
	int a[100002]={};
	int n;
	cin>>n;
	int a1;
	for(int i=0;i<n;i++){
		cin>>a1;
		a[a1]++;
		if(a1>0)a[a1-1]++;
		a[a1+1]++;
	}
	int t=0;
	int k=0;
	for(int i=0;i<100002;i++){
		if(t<a[i]){
			t=a[i];
			k=i;
		}
	}
	cout<<t<<endl;
//
//	for(int i=0;i<201;++i){
//		for(int j=0;j<201;++j){
//			d[i][j]=200000001;
//		}
//	}
//	cin>>n>>m>>s;
//	bool flg=true;
//	int a,b,c;
//	int ct=0;;
//	for(int i=0;i<s;++i){
//		cin>>r[i];
//		ct+=(1<<i);
//	}
//	for(int i=0;i<m;++i){
//		cin>>a>>b>>c;
//		d[a][b]=c;
//		d[b][a]=c;
//	}
//	while(flg){
//		flg=false;
//		for(int i=1;i<n+1;++i){
//			for(int j=1;j<n+1;++j){
//				for(int k=1;k<n+1;++k){
//					if(d[i][j]>(d[i][k]+d[k][j])){
//						flg=true;
//						d[i][j]=d[i][k]+d[k][j];
//					}
//				}
//			}
//		}
//	}
//
//	int t=200000001;
//
//	for(int i=0;i<s;++i){
//		t=min(t,calc(i,ct));
//	}

//	cout<<max(x-t,0)<<endl;

	return 0;
}


Measured memory_bytes: 640
N=int(input())
F=[list(map(int,input().split())) for i in range(N)]
P=[list(map(int,input().split())) for i in range(N)]
ans=-float("inf")
for i in range(1,1 << 10):
  res=0
  for n in range(N):
    count=0
    for j in range(10):
      if i & F[n][j]<<j: count+=1
    res+=P[n][count]
  ans=max(res,ans)
print(ans)

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[200005];
ll B[200005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    REP(i, N) {
        cin >> A[i];
        A[i]--;
    }
    REP(i, N) {
        B[i] = INF;
    }
    ll index = 0;
    ll num = 0;
    while (true) {
        if (B[index] < INF) {
            //cout << index << endl;
            break;
        }
        B[index] = num++;
        index = A[index];
        K--;
        if (K == 0) {
            cout << index + 1 << endl;
            return 0;
        }
    }

    ll base = index;
    REP(i, N) {
        B[i] = INF;
    }
    num = 0;
    while (true) {
        B[index] = num++;
        index = A[index];
        if (index == base) {
            break;
        }
    }

    K %= num;
    REP(i, N) {
        if (K == B[i]) {
            cout << i + 1 << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 6780