akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
#pragma warning(disable:4996)

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int>a(m);
	for (int i = 0; i < m; i++)
		cin >> a[i];
	if (n >= m) {
		cout << 0;
		return 0;
	}
	sort(a.begin(), a.end());
	vector<int>vc;
	for (int i = 1; i < m; i++)
		vc.push_back(abs(a[i] - a[i - 1]));
	sort(vc.begin(), vc.end());
	long long ans = 0;
	for (int i = 0; i <abs(n-m); i++)
		ans += 1LL * vc[i];
	cout << ans;
}


Measured memory_bytes: 1404
import sys

# sys.stdin = open('d1.in')

inf = 10 ** 20


def solve(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    b = n - 1
    while b != 0:
        a = pred[b]
        c = weights[(a, b)]
        if score[b] < score[a] + c:
            return 'inf'
        b = a
    return score[n-1]


def solve2(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    res = score[n-1]

    for step in range(n):
        for edge, c in weights.items():
            a, b = edge
            if score[b] < score[a] + c:
                score[b] = score[a] + c
                pred[b] = a

    if res < score[n-1]:
        return 'inf'
    return res


def main():
    n, m = map(int, input().split())
    weights = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        weights[(a, b)] = c

    res = solve(n, m, weights)
    print(res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3504
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

int dp[110][110] = {};

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int H,W; cin >>H>>W;
    vector<string> S(H);
    REP(i,H){
        cin >> S[i];
    }


    REP(i,H) REP(j,W){
        if(i == 0 && j == 0) continue;
        if(i == 0){
            dp[i][j] = dp[i][j-1] + (S[i][j-1] != S[i][j] ? 1 : 0);
        }else if(j == 0){
            dp[i][j] = dp[i-1][j] + (S[i-1][j] != S[i][j] ? 1 : 0);
        }else{
            int a,b;
            a = dp[i][j-1] + (S[i][j-1] != S[i][j] ? 1 : 0);
            b = dp[i-1][j] + (S[i-1][j] != S[i][j] ? 1 : 0);
            dp[i][j] = min(a,b);
       }
    }
    if(S[0][0] == '#' && S[H-1][W-1] == '#'){
        cout << dp[H-1][W-1] / 2 + 1 << endl;
    }else{
        cout << (dp[H-1][W-1]+1) / 2 << endl;
    }

}


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

using namespace std;

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

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

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
/*bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}*/

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

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


// ***************************CODE**********************//



int main(){


        int n;
        cin >> n;
        vector<int> plus;
        vector<int> mainasu;
        int sum = 0;
        rep(i,n){
                int a;
                cin >> a;
                sum += abs(a);
                if(a > 0){
                        plus.push_back(a);
                }else{
                        mainasu.push_back(a);
                }
        }

        sort(all(plus));
        sort(all(mainasu));

        //1
        if(plus.empty()){
                cout << sum - abs(mainasu.back() * 2) << endl;
                int sz = mainasu.size();
                for(int i = 0; i+1 < sz; i++){
                        cout << mainasu[sz - 1] << " " << mainasu[i] << endl;
                       mainasu[sz-1] -= mainasu[i];
                }
                return 0;
        }

        //2
        if(mainasu.empty()){
                cout << sum - plus[0]*2 << endl;

                for(int i = 1; i+1 < plus.size(); i++){
                        cout << plus[0] << " " << plus[i] << endl;
                        plus[0] -= plus[i];
                }
                cout << plus.back() << " " << plus[0] << endl;
                return 0;
        }

        //3
        cout << sum << endl;
        for(int i = 1; i < plus.size(); i++){
                cout << mainasu[0] << " " << plus[i] << endl;
                mainasu[0] -= plus[i];
        }
        for(int i = 0; i < mainasu.size(); i++){
                cout << plus[0] << " " << mainasu[i] << endl;
                plus[0] -= mainasu[i];
        }
        return 0;




}


Measured memory_bytes: 2424
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=505;
int n,s[N],t[N],u[N],v[N],ans[N][N],a[N][N];
vector<pair<int,int>>r,c;
inline void zh(){cout<<-1<<endl;exit(0);}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<=n;i++)
		cin>>t[i];
	for(int i=1;i<=n;i++)
		cin>>u[i];
	for(int i=1;i<=n;i++)
		cin>>v[i];
	for(int i=0;i<64;i++)
	{
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				a[j][k]=-1;
		r.clear();
		c.clear();
		for(int j=1;j<=n;j++)
		{
			if(!s[j])
			{
				if((u[j]>>i)&1)
					for(int k=1;k<=n;k++)
						a[j][k]=1;
				else
					r.emplace_back(j,0);
			}
			else
			{
				if((~u[j]>>i)&1)
					for(int k=1;k<=n;k++)
						a[j][k]=0;
				else
					r.emplace_back(j,1);
			}
		}
		for(int j=1;j<=n;j++)
		{
			if(!t[j])
			{
				if((v[j]>>i)&1)
				{
					for(int k=1;k<=n;k++)
						if(a[k][j]==0)
							zh();
					for(int k=1;k<=n;k++)
						a[k][j]=1;
				}
				else
					c.emplace_back(j,0);
			}
			else
			{
				if((~v[j]>>i)&1)
				{
					for(int k=1;k<=n;k++)
						if(a[k][j]==1)
							zh();
					for(int k=1;k<=n;k++)
						a[k][j]=0;
				}
				else
					c.emplace_back(j,1);
			}
		}
		if(min(r.size(),c.size())>=2)
		{
			for(int j=0;j<r.size();j++)
				for(int k=0;k<c.size();k++)
					a[r[j].first][c[k].first]=(j+k)&1;
		}
		else if(r.size()==1)
		{
			for(auto p:c)
			{
				int fl=0;
				for(int j=1;j<=n;j++)
					fl|=a[j][p.first]==p.second;
				a[r[0].first][p.first]=fl?r[0].second:p.second;
			}
			int fl=0;
			for(int j=1;j<=n;j++)
				fl|=a[r[0].first][j]==r[0].second;
			if(!fl)
				zh();
		}
		else if(c.size()==1)
		{
			for(auto p:r)
			{
				int fl=0;
				for(int j=1;j<=n;j++)
					fl|=a[p.first][j]==p.second;
				a[p.first][c[0].first]=fl?c[0].second:p.second;
			}
			int fl=0;
			for(int j=1;j<=n;j++)
				fl|=a[j][c[0].first]==c[0].second;
			if(!fl)
				zh();
		}
		else
		{
			for(auto p:r)
			{
				int fl=0;
				for(int j=1;j<=n;j++)
					fl|=a[p.first][j]==p.second;
				if(!fl)
					zh();
			}
			for(auto p:c)
			{
				int fl=0;
				for(int j=1;j<=n;j++)
					fl|=a[j][p.first]==p.second;
				if(!fl)
					zh();
			}
		}
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				ans[j][k]|=(a[j][k]&1)<<i;
	}
	for(int j=1;j<=n;j++)
	{
		for(int k=1;k<=n;k++)
			cout<<ans[j][k]<<' ';
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 9536
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG

using namespace std;
typedef long long ll;
typedef vector<ll> vel;
typedef vector<string> ves;
typedef vector<int> vei;
typedef vector<vector<ll>> vvel;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REP(a, b, m) for (ll a = (ll)(b); a < (ll)(m); a++)

int main() {
    ll n;cin>>n;
    vel A(n);
    rep(i,n) {
        cin>>A[i];
    }
    ll q;cin>>q;
    vel B(q),C(q);
    rep(i,q) {
        cin>>B[i]>>C[i];
    }
    vel memo(1000000,0);
    rep(i,n) {
        memo[A[i]]++;
    }
    ll ans;
    rep(i,n) {
        ans+=A[i];
    }
    rep(i,q) {
        ans=ans-B[i]*memo[B[i]]+C[i]*memo[B[i]];
        memo[C[i]]+=memo[B[i]];
        memo[B[i]]=0;
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 13460
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string n;
	cin>>n;
	int a=0,b=0;
	for(int i=0;i<n.size();i++)
	{
		if(n[i]!='0' +i%2) ++a; 
    }
	if(a>n.size()/2) a=n.size()-a; 
	cout<<a<<endl;
    return 0;	
} 

Measured memory_bytes: 512
n = int(input())
red = [tuple(map(int, input().split())) for _ in range(n)]
blue = [tuple(map(int, input().split())) for _ in range(n)]

red.sort(key=lambda x:x[1], reverse=True)
blue.sort()
chk = [False] * n

for b in blue:
    for i, r in enumerate(red):
        if chk[i]:
            continue
        elif r[0] < b[0] and r[1] < b[1]:
            chk[i] = True
            break
print(sum(chk))



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

int main(){
	int s[101][101] = {0};
	int	i, j, r, c;
	
	cin >> r >> c;
	for(i = 0; i < r; i++){
		for(j = 0; j < c; j++){
			cin >> s[i][j];
			s[i][c] += s[i][j];
			s[r][j] += s[i][j];
		}
		s[r][c] += s[i][c];
	}
	
	for (i = 0; i < r + 1; i++){
		for(j = 0; j < c + 1; j++){
			cout << s[i][j];
			if(j != c){
				cout << " ";
			}
		}
		cout << endl;
	}

 	return 0;
}

Measured memory_bytes: 3116
n,m = map(int, input().split())
vote_ls = list(map(int, input().split()))

top_vote_ls = []
selectable = (1/(4*m))*sum(vote_ls)

for i in range(0, m):  
  max = 0
  for j in range(len(vote_ls)):      
    if vote_ls[j] > max: 
      max = vote_ls[j]; 
  vote_ls.remove(max); 
  if max >= selectable:
    top_vote_ls.append(max) 

if len(top_vote_ls) >= m: 
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main()
{
    string s1,s2,s3;
    char a,b,c;
    cin>>s1>>s2>>s3;
    a=s1[0],b=s2[0],c=s3[0];
    cout<<a<<b<<c;
    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

int main(){

    int n=1,x;

    vector<int> v;

    while(n!=0){
        cin >> n >> x;

        int s=0;

        

        if(n!=0){
            for(int i=1;i<n-1;i++){
                for(int j=i+1;j<n && i<j;j++){
                    for(int k=j+1;k<n+1 && j<k;k++){
                        if(i+j+k == x) s+=1;
                    }
                }
            }

            v.push_back(s);
        }
    }

    for(int i=0;i<v.size();i++){
        cout << v[i] << endl;
    }

}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define fix(n) cout<<fixed<<setprecision(n);
using namespace std;
//using bint=boost::multiprecision::cpp_int;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  int n; cin>>n;
  int a=0,b=0;
  rep(i,0,n){
    string s,t; cin>>s>>t;
    if(s==t){
      a++;
      b++;
    }
    else if(s>t) a+=3;
    else b+=3;
  }
  co(a<<" "<<b);
  
  return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define for1(i, a, b) for(i = a; i <= b; ++i)
#define for0(i, a, b) for(i = a; i < b; ++i)
#define forw1(i, a, b) for(i = a; i >= b; --i)
#define forw0(i, a, b) for(i = a - 1; i >= b; --i)
#define fora(v, a) for(auto v : a)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

using namespace std;
using cd = complex<double>;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<cd> vcd;
typedef vector<ii> vii;
typedef vector<vector<int> > vvi;

const int modd1 = 1e9 + 7, modd2 = 998244353, maxn = 10, K = 26, inf = 1e9, infll = 1e18;
const double pi = acos(-1);

void solve(){
    int a, b; cin >> a >> b; cout << a * b;
}

signed main() {
    //freopen(".INP", "r", stdin); 
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

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

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

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

  int k; cin >> k;
  string s; cin >> s;
  if(SZ(s) <= k) {
    cout << s << endl;
  } else {
    cout << s.substr(0, k) << "..." << endl;
  }

}
























Measured memory_bytes: 3656
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<ll> a(n), f(N), s;
    for (ll &e : a)
        cin >> e, f[e]++;
    ll c = n;
    if (f[1])
        return cout << !(f[1] - 1), 0;
    for (ll e : a)
    {
        if (f[e] == 1)
            for (ll j = 2; j * j <= e; j++)
            {
                if (e % j == 0 && (f[j] || f[e / j]))
                {
                    c--;
                    break;
                }
            }
        else
            c--;
    }
    cout << c;
}

Measured memory_bytes: 12640
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#pragma comment(linker, "/STACK:400000000")

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(it=X.begin();it!=X.end();it++)
#define iss istringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sst stringstream
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int L,H,perm[11];
struct hint{
    int h,b,used[11],pos[11];
} h[111];

bool comp(hint a,hint b){
    return a.h > b.h;
}

int main(){
	while(cin>>L>>H && L){
        vi ans;
        rep(i,10)perm[i]=i;
        rep(i,H){
            fill(h[i].used,h[i].used+10,0);
            fill(h[i].pos,h[i].pos+10,0);
            char c;
            rep(j,L){
                cin>>c;
                int x=c-'0';
                h[i].used[x]=1;
                h[i].pos[j]=x;
            }
            cin>>h[i].h>>h[i].b;
        }
        sort(h,h+H,comp);
        int prevlast=-1;
        do{
            if(perm[L-1]==prevlast)continue;
            rep(i,H){
                int hit=0,hitblow=0;
                rep(j,L){
                    hit+= h[i].pos[j]==perm[j];
                    hitblow+= h[i].used[perm[j]];
                }
                if(hit!=h[i].h || hitblow-hit!=h[i].b)goto fail;
            }
            if(ans.sz>0){
                cout<<"NO\n";
                goto end;
            }
            rep(i,L)ans.pb(perm[i]);
            fail:;
            prevlast=perm[L-1];
        }while(next_permutation(perm,perm+10));
        if(ans.sz>0){
            rep(i,L)cout<<ans[i];
            cout<<endl;
        }else cout<<"NO\n";
    end:;
    }
}

Measured memory_bytes: 912
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		// for (; solver.hasNext();) {
		// solver.readBody(in.readLine());
		// }
		// solver.solve();
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split(" ");
		// N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
		int a = Integer.parseInt(strArr[0]);
		int b = Integer.parseInt(strArr[1]);
		int c = Integer.parseInt(strArr[2]);
		if (a == b && a == c)
			System.out.println("Yes");
		else
			System.out.println("No");
	}

	public boolean hasNext() {
		return cnt < N;
	}

	public void readBody(String str) {
		// System.out.println(str);
		cnt++;
	}

	public void solve() {

	}
}


Measured memory_bytes: 22484
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807

#define int long long
int gcd(int a, int b){
    if(b > a) swap(a, b);
    int tmp;
    while(b != 0){
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int p[100], q[100], r[100], s[100];
int dp[100] = {};
int solve(int now){
    if(dp[now] != 0) return dp[now];
    if(r[now] != -1 && s[now] != -1){//両端が棒と繋がっていた場合
        int a1 = solve(r[now]);
        int b1 = solve(s[now]);
        int a2 = a1;
        int b2 = b1;
        while(a2*p[now] != b2*q[now]){
            if(a2*p[now] < b2*q[now]) a2 += a1;
            if(a2*p[now] > b2*q[now]) b2 += b1;
        }
        return dp[now] = a2 + b2;
    }
    if(r[now] == -1 && s[now] == -1){//両端がおもりの場合
        return dp[now] = p[now] + q[now];
    }
    if(r[now] != -1 && s[now] == -1){//左は棒、右はおもり
        int a1 = solve(r[now]);
        int b1 = 1;
        int a2 = a1;
        int b2 = b1;
        while(a2*p[now] != b2*q[now]){
            if(a2*p[now] < b2*q[now]) a2 += a1;
            if(a2*p[now] > b2*q[now]) b2 += b1;
        }
        return dp[now] = a2 + b2;
    }
    if(r[now] == -1 && s[now] != -1){//左はおもり、右は棒
        int a1 = 1;
        int b1 = solve(s[now]);
        int a2 = a1;
        int b2 = b1;
        while(a2*p[now] != b2*q[now]){
            if(a2*p[now] < b2*q[now]) a2 += a1;
            if(a2*p[now] > b2*q[now]) b2 += b1;
        }
        return dp[now] = a2 + b2;
    }
}

#undef int
int main(){
    #define int long long
    iostream::sync_with_stdio(false);
    
    while(true){
        int n;
        cin >> n;
        if(n == 0) return 0;

        for(int i=0; i<n; i++){
            cin >> p[i] >> q[i] >> r[i] >> s[i];
            int g = gcd(p[i], q[i]);
            p[i] /= g;
            q[i] /= g;
            r[i]--;
            s[i]--;
            dp[i] = 0;
        }

        int ans = 0;
        for(int i=0; i<n; i++){
            ans = max(ans, solve(i));
        }
        cout << ans << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3016
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int num[26]={0};
    for(int i=0;i<s.size();i++){
        num[s.at(i)- 'a']++;
    }
    for(int i=0;i<26;i++){
        if(num[i] == 0){
            cout << char(i + 'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

Measured memory_bytes: 512
S = int(input())
# 3-(3) 4-(4) 6-((3,3),(6))7-((3,4),(4,3),(7)) 8-((4,4),(3,5),(5,3),(8)) 9-((3,3,3),(3,6),(4,5),(5,4),(6,3),(9))
# 10-((3,3,4)*3,(3,7),(4,6)...(7,3),(10)))
# S//3こ~1個の項でできている。
# １この項の要素数 = 1, 2個の項の要素数 = (S-3)~(3)個、 3個の項の要素数=(3,3,3)
L = 10**9+7
def calc_comb(n,k):
    ans = 1
    for i in range(n,n-k,-1):
        ans *= i
        ans %= L
    for i in range(1,k+1):
        ans *= pow(i,L-2,L)
        ans %= L
    return ans
if S<=2:
    print(0)
    exit()
out = 0
for i in range(0,S//3):
    out += calc_comb(S-3*(i+1)+i,i)
    out %= L
print(out)








Measured memory_bytes: 9136
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;
struct edge { LL to, cost; };

const LL inf = 11234567890123456;
std::vector<LL>dist;
std::vector<std::vector<edge>>G;
bool bellman_ford(LL n, LL s, LL t)
{
    std::fill(dist.begin(), dist.end(), inf);
    dist[s] = 0;
    rep(i, 2 * n)
    {
        for (LL v = 1; v <= n; ++v)
        {
            for (auto e : G[v])
            {
                if (dist[v] != inf && dist[e.to] > dist[v] + e.cost)
                {
                    dist[e.to] = dist[v] + e.cost;
                    if (i >= n - 1 && e.to == t) return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    LL N, M, P;
    in >> N >> M >> P;
    std::vector<LL>a(M), b(M), c(M);
    rep(i, M) in >> a[i] >> b[i] >> c[i];
    
    dist.resize(N + 1); G.resize(N + 1);
    rep(i, M) G[a[i]].push_back({ b[i],-c[i] + P });
    if (bellman_ford(N, 1, N)) out << -1 << std::endl;
    else out << std::max(0ll, -dist[N]) << std::endl;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    vector<long long> v(6);
    for (int i = 0; i < 6; ++i)
        cin >> v[i];

    long long min_n = v[1];
    for (int i = 2; i < 6; ++i)
        min_n = min(min_n, v[i]);

    long long time = (v[0] + min_n - 1) / min_n + 4;
    cout << time << '\n';
}


Measured memory_bytes: 256
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <queue>
#include <complex>
#include <climits>
#include <cstring>
#include <cstdlib>

typedef long long ll;

using namespace std;

#define INF 1000000

int H, W, N;
int sx, sy;	
int res = 0;
int d[1100][1100];
char maze[1100][1100];
pair<int, int> cheese[10];

void bfs(int HP){
	queue<pair<int, int> > que;

	sx = cheese[HP-1].first, sy = cheese[HP-1].second;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			d[i][j] = INF;
		}
	}	
	que.push(pair<int, int>(sx, sy));
	d[sx][sy] = 0;

	while(que.size()){
		pair<int, int> p = que.front(); que.pop();
		if((maze[p.first][p.second] - '0') == HP) break;
		for(int dx=-1; dx<=1; ++dx)
			for(int dy=-1; dy<=1; ++dy){
				if(abs(dx-dy) != 1) continue;
				int nx = p.first + dx, ny = p.second + dy;
				if(0 <= nx && nx < H && 0 <= ny && ny < W && maze[nx][ny] != 'X' && d[nx][ny] == INF){
					que.push(pair<int, int>(nx, ny));
					d[nx][ny] = d[p.first][p.second] + 1;
				}
			}
	}

	if(HP == N){
		res += d[cheese[HP].first][cheese[HP].second];
		return;
	}

	res += d[cheese[HP].first][cheese[HP].second];
	bfs(HP+1);
	return;
}

int main(void){
	cin >> H >> W >> N;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			cin >> maze[i][j];
			if(maze[i][j] - '0' >= 1 && maze[i][j] - '0' <= N){
				cheese[maze[i][j] - '0'] = pair<int, int>(i, j);
			} else if(maze[i][j] == 'S'){
				cheese[0] = pair<int, int>(i, j);
			}
		}
	}

	bfs(1);
	int r = res;
	cout << r << endl;
	return 0;
}

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

#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384


int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;} 
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}    //最大公約数
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}     //最小公倍数
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;} //コンビネーション
int nHr(int a,int b){return nCr(a+b-1,b);}       // 重複組み合わせ
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}  //階乗
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} // a~bまでの階乗
int dsum(int x){int r=0;while(x){r+=(x%10);x/=10;}return r;}   //数字の各位の和
int dsumb(int x,int b){int r=0;while(x){r+=(x%b);x/=b;}return r;}  // b進数の各位の和？
int sankaku(int x){return ((1+x)*x)/2;} //三角数 xまでの和

//以下long long ver
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llnHr(long long a,long long b){return llnCr(a+b-1,b);}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long lldsum(long long x){long long r=0;while(x){r+=(x%10);x/=10;}return r;}
long long lldsumb(long long x,long long b){long long r=0;while(x){r+=(x%b);x/=b;}return r;}
long long llsankaku(long long x){return ((1+x)*x)/2;}

//double
double dbmax(double a,double b){if(a>b){return a;}return b;}
double dbmin(double a,double b){if(a<b){return a;}return b;}
double dbzt(double a,double b){return dbmax(a,b)-dbmin(a,b);}


typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) ; for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
bool is_prime (int x){
  if (x<=1) return false ;
  for (int i=2 ; i*i<=x ; i++){
    if (x%i==0) return false ;
  }
   return true;
}
string alpha = "abcdefghijklmnopqrstuvwxyz" ;

 
/*CODE START HERE*/
int main() {
 int64_t a,b,c,k;
  cin >> a >> b >> c >> k;
  if ( abs (a- b ) > 1000000000000000000 ) {
    cout << "Unfair" << endl;
    return 0;
  }
  if ( k%2 == 1){
    cout << b-a << endl;
  }else cout << a-b << endl;
}

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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    string x="",y="";
    int a,b;
    cin>>a>>b;
    for(int i=0; i<b; i++)
    {
        x+='0'+a;
    }

    for(int i=0; i<a; i++)
    {
        y+='0'+b;
    }
    for(int i=0; i<min(a,b); i++)
    {
        if(x[i]<y[i])
        {
            cout<<x;
            return 0;
        }
        else  if(y[i]<x[i])
        {
            cout<<y;
            return 0;
        }
    }
    if(x.size()>y.size())
        cout<<y;
    else
        cout<<x;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    int max=-10000;
    if(a+b>max) max = a+b;
    if(a-b>max) max = a-b;
    if(a*b>max) max = a*b;
    cout << max << endl;
}

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

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }


/*
--------------------------------------------

	type

--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

/*
--------------------------------------------

	container

--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())

/*
--------------------------------------------

	repetition

--------------------------------------------
*/
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPinit(a,n) for(int i=a; i<n; i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

/*
--------------------------------------------

	constant

--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

/*

	Optimizer

*/
//#pragma GCC optimize("Ofast")

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

  int N;
  cin >> N;
  
  // cout << N << ' ';
  if((N % 1111 == 0) || ((N/10)%111 == 0) || ((N%1000)%111 == 0) || (N % 1000 == 0)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

#define MAX 1000100

signed main(){
    vector<int> v;
    int pr[MAX+1]={0};
    int N;

    cin>>N;

    for(int i=2;i<=MAX;i++){
        if(pr[i]==0){
            v.push_back(i);
            for(int j=i;j<=MAX;j+=i){
                pr[i]=1;
            }
        }
    }

    int ans=0;
    for(int i=0;i<v.size();i++){
        int sum=0;
        while(N%v[i]==0){
            sum++;
            N/=v[i];
        }
        int add=0;
        int mnus=1;
        while(1){
            sum-=mnus;
            if(sum<0) break;
            add++;
            mnus++;
        }
        ans+=add;
    }

    if(N!=1) ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 19096
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
typedef pair<string, int> P;
#define mod 1e9 + 7;
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}


int main()
{
	ios_base::sync_with_stdio(false);
	ll n, m, a, b, ans = 0;
	cin >> n >> m;
	vi x(m), y(m), ball(n + 1);
	vector<bool> ok(n+1);
	rep(i, n + 1) {
		ball[i] = 1;
		ok[i] = false;
	}
	ok[1] = true;
	rep(i, m) {
		cin >> x[i] >> y[i];
		ball[x[i]]--;
		ball[y[i]]++;
		if (ok[x[i]]) {
			ok[y[i]] = true;
		}
		if (ball[x[i]] == 0) ok[x[i]] = false;
		//rep(j, n+1) cout << ok[j] << " ";
		//cout << "\n";
		//cout << ans << endl;
	}
	rep(i, n + 1) if (ok[i]) ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define fi first
#define se second
#define LL long long

using namespace std;
const int maxn = 2e5 + 5;
typedef pair<int, int> P;

P a[maxn], b[maxn];
int v[maxn];

vector<P> l, r;

int main() {
#ifdef TT
    freopen("xxx.in", "r", stdin);
#endif // TT
    int n, i, j, k, c;
    LL tot = 0;
    scanf("%d", &n);
    for(i = 0;i < n; i++) {
        scanf("%d%d", &a[i].fi, &b[i].fi);
        a[i].se = b[i].se = i;
    }
    sort(a, a + n);
    sort(b, b + n);
    i = j = 0;
    while(i + j < n) {
        c = min(a[i].fi, b[j].fi);
        if(a[i].fi < b[j].fi) tot += a[i++].fi;
        else tot += b[j++].fi;
    }
    while(i < n && a[i].fi == c) i++;
    while(j < n && b[j].fi == c) j++;
    for(k = 0;k < i; k++) v[a[k].se]++;
    for(k = 0;k < j; k++) v[b[k].se]++;
    for(k = 0;k < n; k++) {
        if(v[k] > 1) break;
    }
    if(i + j > n || (k < n) || i == 0 || j == 0) {
        printf("%lld\n", tot);
        return 0;
    }
    //cout<<i<<" "<<j<<" "<<tot<<endl;
    if(i == 1 || a[i - 1].se != b[n - i].se) l.push_back(P(a[i - 1].fi, b[n - i].fi));
    else {
        l.push_back(P(a[i - 1].fi, b[n - i + 1].fi));
        l.push_back(P(a[i - 2].fi, b[n - i].fi));
    }
    if(j == 1 || b[j - 1].se != a[n - j].se) r.push_back(P(b[j - 1].fi, a[n - j].fi));
    else {
        r.push_back(P(b[j - 1].fi, a[n - j + 1].fi));
        r.push_back(P(b[j - 2].fi, a[n - j].fi));
    }
    LL ans = 1e18;
    for(auto u:l) {
        for(auto v:r) {
            //cout<<u.fi<<" "<<u.se<<" "<<v.fi<<" "<<v.se<<endl;
            ans = min(ans, tot - max(u.fi, v.fi) + min(u.se, v.se));
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

typedef long long ll;
typedef pair<int,int> p_int;
typedef pair<ll,ll> p_ll;
typedef tuple<ll,ll,ll> t3_ll;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const ll inf = 1e9+7;

int main() {
	int n;
	cin >> n;
	ll a[n],b[n],c[n];
	ll les=0;
	ll pls=0;
	ll sum=0;
	ll ans=0;
	ll cnt=0;
	for (int i = 0;i < n;i++) {cin >> a[i];}
	for (int i = 0;i < n;i++) {cin >> b[i];c[i] = a[i]-b[i];if (c[i] < 0) {les+=abs(c[i]);cnt++;}sum+=c[i];}
	sort(c,c+n);
	if (sum < 0) {
		cout << -1 << endl;
		return 0;
	} else {
		int i = 0;
		while (pls < les) {
			i++;
			pls+=c[n-i];
			// cout << pls << " " << les;
		}
		cnt+=i;
		for (int i = 0;i < n;i++) {
			// cout << a[i]-b[i] << " ";
		}
		// cout << endl;
		cout << cnt << endl;
		return 0;
	}
}

Measured memory_bytes: 2560
import java.util.*;

public class Main {

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 0;
		while (true) {
			++num;
			int n = sc.nextInt();
			int t = sc.nextInt();
			int k = sc.nextInt();
			if (n == 0 && k == 0 && t == 0)
				break;
			ArrayList<Edge>[] g = new ArrayList[n];
			for (int i = 0; i < n; ++i)
				g[i] = new ArrayList<>();
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			for (int i = 0; i < n - 1; ++i) {
				int a = sc.nextInt() - 1;
				int b = sc.nextInt() - 1;
				int c = sc.nextInt();
				g[a].add(new Edge(a, b, c));
				g[b].add(new Edge(b, a, c));
			}

			boolean[] base = new boolean[n];
			for (int i = 0; i < t; ++i) {
				int a = sc.nextInt() - 1;
				pq.addAll(g[a]);
				base[a] = true;
			}

			DJSet ds = new DJSet(n);

			ArrayList<Edge> pending = new ArrayList<>();
			while (!pq.isEmpty()) {
				Edge e = pq.poll();
				if (ds.equiv(e.dst, e.src))
					continue;
				if (base[e.dst] || ds.size(e.dst) > 1)
					pending.add(e);
				else {
					if (ds.setUnion(e.src, e.dst)) {
						pq.addAll(g[e.dst]);
					}

				}
			}

			Collections.sort(pending);

			long ans = 0;
			int len = pending.size();
			for (int i = 0, j = 0; j < k; ++i) {
				Edge e = pending.get(len - 1 - i);
				if (ds.equiv(e.src, e.dst))
					continue;
				ans += e.cost;
				ds.setUnion(e.src, e.dst);
				++j;
			}
			System.out.println("Case " + num + ": " + ans);
		}
	}

	static class Edge implements Comparable<Edge> {
		int src;
		int dst;
		int cost;

		public Edge(int src, int dst, int cost) {
			this.src = src;
			this.dst = dst;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return -Integer.compare(this.cost, o.cost);
		}

	}

	static class DJSet {
		int n;
		int[] upper;

		public DJSet(int n) {
			this.n = n;
			upper = new int[n];
			Arrays.fill(upper, -1);
		}

		int root(int x) {
			return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
		}

		boolean setUnion(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (upper[x] < upper[y]) {
					int d = x;
					x = y;
					y = d;
				}
				upper[y] += upper[x];
				upper[x] = y;
			}
			return x != y;
		}

		boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		int size(int x) {
			return -upper[root(x)];
		}

	}
}

Measured memory_bytes: 191672
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

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


int main(){
    bool north = false, west = false, south = false, east = false;
    string S; cin >> S;
    REP(i, S.length()){
        switch(S[i]){
            case 'N':
                north = true;
                break;
            case 'W':
                west = true;
                break;
            case 'S':
                south = true;
                break;
            case 'E':
                east = true;
                break;
        }
    }
    cout << (((north^south)||(east^west)) ? "No" : "Yes") << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}

/*Coding Space*/
int main(){
  ll n; cin >> n;
  ll ans = 0;
  rep(i,n){
    ll a; cin >> a;
    while(!(a&1)){ans++; a >>= 1;}
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>

using namespace std;


int main(int argc, char *argv[]) {
	int n, s;
	cin >> n >> s;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}
	const int mod = 998244353;
	unordered_map<int, pair<long long int, long long int>> um1, um2;
	// [count][index sum]
	um1[0] = make_pair(0, 0);
	long long int res = 0;
	for (int i = 0; i < n; i++) {
		um2 = um1;
		for (auto p : um1) {
			if (p.first == 0) {
				if (v[i] == s) {
					res += (i + 1) * (n - i) % mod;
					res %= mod;
					continue;
				}
				um2[v[i]].first += 1;
				um2[v[i]].second += i;
				continue;
			}
			if (p.first + v[i] < s) {
				um2[p.first + v[i]].first += p.second.first;
				um2[p.first + v[i]].first %= mod;
				um2[p.first + v[i]].second += p.second.second % mod;
				um2[p.first + v[i]].second %= mod;
			} else if (p.first + v[i] == s) {
				res += (p.second.second + p.second.first) % mod * (n - i) % mod;
				res %= mod;
			}
		}
		um1 = um2;
	}
	cout << res << endl;
}









Measured memory_bytes: 640
str0 = raw_input()
q = int(raw_input())

for i in xrange(q):
  # print "###########################"
  # print "str0 = " + str0
  line = raw_input().split(" ")
  temp = str0[int(line[1]):int(line[2])+1]
  if line[0] == "print":
    print temp
  elif line[0] == "reverse":
    temp2 = [] 
    # print "temp = " + temp
    for j in xrange(len(temp)):
      temp2.append(temp[len(temp) - j - 1])
    str0 = str0[:int(line[1])] + "".join(temp2) + str0[int(line[2]) + 1:]
    # print "str0 = " + str0
  elif line[0] == "replace":
    str0 = str0[:int(line[1])] + line[3] + str0[int(line[2]) + 1:]
    # print "str0 = " + str0

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

using namespace std;


double rast(double x1,double y1,double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}



int main()
{
   // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);

    int a,b,c;
    cin >> a >> b >> c;
    a-=b;
    cout << max(0,c-a);
}


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


int main(){
    int X,A,B;
    cin >> X >> A >> B;
    if(B<=A) cout << "delicious" << endl;
    else if(B<=A+X) cout << "safe" << endl;
    else cout << "dangerous" << endl;
}   

Measured memory_bytes: 256
N, K = map(int,input().split())
S = str(input())

if K == 1:
  ans = S[0].lower() + S[1:]
elif K == N:
  ans = S[:N-1] + S[N-1].lower()
else:
  ans = S[:K-1] + S[K-1].lower() + S[K:]
  
print(ans)

Measured memory_bytes: 3060