akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;

int n;
lli a[200000],b[200000],ta[200000],tb[200000];

int find(lli v1,lli v2) {
	int l=lower_bound(ta,ta+n,v1)-ta;
	int r=lower_bound(ta,ta+n,v2)-ta;
	return (r-l)%2;
}
int check(lli val) {
	for(int i=0;i<n;i++) {
		ta[i] = a[i]%(2*val);
		tb[i] = b[i]%(2*val);
	}
	sort(ta,ta+n); sort(tb,tb+n);
	
	int res=0;
	for(int i=0;i<n;i++) {
		res ^= find(val-tb[i], val*2-tb[i]) ^ find(val*3-tb[i], val*4-tb[i]);
	}
	return res%2;
}
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",a+i);
	for(int i=0;i<n;i++) scanf("%lld",b+i);

	lli ans=0;
	for(int i=0;i<30;i++) {
		ans += check(1<<i) << i;
	}
	printf("%lld\n",ans);
	
	return 0;
}

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

using namespace std;
const int MAXN = 1e4 + 3;
vector<int> graph[MAXN];
vector<int> c;
int ans[MAXN];
int ii = 0;

void dfs(int cur, int parent) {
  ans[cur] = c[ii];
  for (int i = 0; i < (int)graph[cur].size(); ++i) {
    if(graph[cur][i] != parent) {
      ii++;
      dfs(graph[cur][i], cur);
    }
  }
}

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

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

  c.resize(N);
  for (int i = 0; i < N; ++i) cin >> c[i];
  sort(c.begin(), c.end(), greater<int>());

  int minNode = 1e9;
  int idx;
  for (int i = 0; i < N; ++i) {
    int s = (int)graph[i].size();
    if (s < minNode) {
      idx = i;
      minNode = s;
    }
  }
  dfs(idx, idx);
  int sum = 0;
  for (int i = 1; i < N; ++i) sum += c[i];
  cout << sum << endl;
  for (int i = 0; i < N; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 1536
import sys
import numpy as np

reatInt = lambda: int(sys.stdin.readline())
reatIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]


n = reatInt()
hs = reatIntN()

maxv = 0
ret = 0
for h in hs:
    if maxv <= h:
        ret += 1
        maxv = h
print(ret)

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

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

const int N = 18, P = 1000000007;

int n, p[1 << N], dep[1 << N], fw[1 << N][N], w[1 << N], ans;

int main() {
	read(n);
	for (int i = 1 << (n - 1); i < (1 << n); ++i) {
		read(p[i]);
		--p[i];
		p[i] |= 1 << (n - 1);
	}
	for (int i = (1 << (n - 1)) - 1; i; --i) {
		dep[i] = dep[i << 1] + 1;
	}
	for (int i = 1; i < (1 << n); ++i) {
		fw[i][0] = i;
		for (int j = 1; j < n - dep[i]; ++j) {
			fw[i][j] = 1ll * fw[i][j - 1] * (i >> j) % P;
		}
	}
	for (int i = 1; i < (1 << (n - 1)); ++i) {
		int u = i << 1, v = i << 1 | 1;
		for (int k = 0; k < (1 << dep[u]); ++k) {
			int t = u << dep[u] | k;
			int s = fw[t][dep[i]];
			t = p[t];
			while (t) {
				s = 1ll * s * t % P;
				w[t] = (w[t] + s) % P;
				t >>= 1;
			}
		}
		for (int k = 0; k < (1 << dep[v]); ++k) {
			int t = v << dep[v] | k;
			int s = fw[t][dep[v]];
			t = p[t];
			while (t > 1) {
				s = 1ll * s * t % P;
				ans = (ans + 1ll * s * (t >> 1) % P * w[t ^ 1]) % P;
				t >>= 1;
			}
		}
		for (int k = 0; k < (1 << dep[u]); ++k) {
			int t = u << dep[u] | k;
			t = p[t];
			while (t) {
				w[t] = 0;
				t >>= 1;
			}
		}
	}
	print(ans);
}

Measured memory_bytes: 24908
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(n)]

ls.sort()
ans = 0
numOfDrink = 0
for (a, b) in ls:
    if numOfDrink + b <= m:
        ans += a * b
        numOfDrink += b
    else:
        ans += a * (m-numOfDrink)
        break

print(ans)

Measured memory_bytes: 27756
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n;
	cin>>n;
	ll a[200000];
	ll pr0=-1;
	bool one=1;
	for(int i=0; i<n; i++){
		cin>>a[i];
		if(pr0>=a[i]){
			one=0;
		}
		pr0=a[i];
	}
	if(one){
		cout<<1<<endl;
		return 0;
	}
	int x1=2, x2=n;
	while(x1!=x2){
		int x=(x1+x2)/2;
		map<ll, int> mp;//mp[d]=d桁目の値
		ll pr=-1;
		bool muri=0;
		for(int i=0; i<n; i++){ //a[i]桁目に1足す
			if(pr<a[i]){
				//mp[a[i]]=0;
				pr=a[i];
				continue;
			}
			pr=a[i];
			while(!mp.empty()){
				auto itr2=mp.end();
				itr2--;
				if((itr2->first)>a[i]){
					mp.erase(itr2);
				}else{
					break;
				}
			}
			auto itr=mp.find(a[i]);
			if(itr==mp.end()){
				mp[a[i]]=1;
				continue;
			}
			if((itr->second)<x-1){
				(itr->second)++;
				continue;
			}
			itr->second=0;
			ll d=a[i]-1;
			while(1){
				if(d<=0){
					muri=1;
					break;
				}
				auto itr1=mp.find(d);
				if(itr1==mp.end()){
					mp[d]=1;
					break;
				}
				if((itr1->second)<x-1){
					(itr1->second)++;
					break;
				}
				itr1->second=0;
				d--;
			}
			if(muri) break;
		}
		if(muri) x1=x+1;
		else x2=x;
	}
	cout<<x1<<endl;
	return 0;
}

Measured memory_bytes: 1792
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    S = input()
    N = int(S)

    f = 0
    for x in S:
        f += int(x)

    if N % f == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 61956
#include <iostream>
#include <string.h>
using namespace std;

int mod = 1e7;

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

  //int tc;
  //cin >> tc;

  string s, t;
  cin >> s >> t;
  
  int rep = 0;
  for (int k = 0; k < (int)s.length() - (int)t.length() + 1; k++){
    int rp = 0;
    for(int i = k, j = 0; j < t.length(); j++, i++)
      rp = t[j] == s[i] ? rp + 1 : rp;
    rep = rp > rep ? rp : rep;
  }
  cout << t.length() - rep << "\n";
}

Measured memory_bytes: 3640
#include<stdio.h>
int w[201000], n, bb, ee, r, mid, p[201000];
int c,d;
int main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=2*n-1;i++)scanf("%d",&w[i]);
    w[0]=w[1],w[2*n]=w[2*n-1];
    bb = 1, ee = 2*n-1;
    while(bb<=ee){
        mid = (bb+ee)>>1;
        for(i=0;i<=2*n;i++){
            if(w[i]>=mid)p[i]=1;
            else p[i]=0;
        }
        for(i=n;i>=1;i--){
            if(p[i]==p[i-1]){
                c=p[i],d=n-i;
                break;
            }
        }
        for(i=n;i<2*n;i++){
            if(p[i]==p[i+1]){
                if(d>i-n)d=i-n,c=p[i];
                break;
            }
        }
        if(c==1){
            r=mid;
            bb = mid+1;
        }
        else ee = mid-1;
    }
    printf("%d\n",r);
}

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

typedef pair<long long, long long> P;

int main(){
  int n, m;
  long long a, b;
  priority_queue<P,vector<P>, greater<P>> Q;
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    Q.push(P(a, b));
  }
  long long cnt=0, ans=0;
  while(1){
    long long tmpa=Q.top().first;
    long long tmpb=Q.top().second;
    Q.pop();
    ans += tmpa * min (m - cnt, tmpb);
    cnt += tmpb;
    if(cnt>=m)break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2420
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<double,int,double> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf=sizeof(Def)==sizeof(long long)?2e18:1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	ll n;
	cin>>n;
	vi out(50,49+n/50);
	n-=n/50*50;
	rep(i,n){
		rep(j,50)if(i==j)out[j]+=50;
		else out[j]--;
	}
	cout<<50<<endl;
	rep(i,50)cout<<(i?" ":"")<<out[i];cout<<endl;
}








Measured memory_bytes: 256
import { readFileSync } from 'fs'

function main(input: string) {
  const [n, values, costs] = input.trim().split('\n').map(v => v.split(' ').map(Number))


  const result = values
    .map((v, i) => v - costs[i])
    .filter(v => v > 0)
    .reduce((sum, v) => sum + v, 0)

  console.log(result)
}

main(readFileSync('/dev/stdin', 'utf8').trim())


Measured memory_bytes: 7500
n, m = map(int, input().split())
cit = []
y = [1]*n
for i in range(m):
    cit.append([i] + list(map(int, input().split())))
cit.sort(key=lambda x: x[2])
for i in range(m):
    cit[i] += ["0"*(6-len(str(cit[i][1])))+str(cit[i][1]) +
               "0" * (6 - len(str(y[cit[i][1]-1]))) + str(y[cit[i][1]-1])]
    y[cit[i][1]-1] += 1
cit.sort()
for i in range(m):
    print(cit[i][-1])


Measured memory_bytes: 35548
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>

#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

using namespace std;

int main(){

  int m,f,r;

  while(1){
    cin >>m >>f >>r;

    if(m==-1&&f==-1&&r==-1) break;
    else if(m==-1 || f==-1) cout <<"F" <<endl;
    else if(80<=m+f) cout <<"A" <<endl;
    else if(65<=m+f) cout <<"B" <<endl;
    else if(50<=m+f) cout <<"C" <<endl;
    else if(30<=m+f && 50<=r) cout <<"C" <<endl;
    else if(30<=m+f && r<50) cout <<"D" <<endl;
    else if(0<=m+f) cout <<"F" <<endl;
  }
  return 0;
}

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

int main(void) {
	int N, M;
	cin >> N >> M;
//	vector <long long> A(N);
	priority_queue <int> que;
	for (int i = 0; i < N; i++) {
		int Ai;
		cin >> Ai;
		que.push(Ai);
//		A[i] = Ai;
	}
	for (int i = 0; i < M; i++) {
//		sort(A.begin(), A.end(),
//			[](const long long& x, const long long& y) {return x > y;});
		int A = que.top();
		que.pop();
		A /= 2;
		que.push(A);
//		A[0] = A[0] / 2;
	}
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		ans += que.top();
		que.pop();
		//ans += A[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 892
//=======================//
// coder: Andy - Tohrumi //
//=======================//
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fastio ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define mp make_pair
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(__typeof(b) i = a; i < b; i++)
#define Rep(i, a, b) for(__typeof(a) i = a; i > b; i--)
 
typedef vector<int> vi;		typedef vector<ll> vl;
typedef pair<int, int> ii; 	typedef vector<ii> vii;
 
// code start here //
 
const int N = 100005;
vi tree[N];
queue<int> q; 
ii range[N];
bool check;
 
void bfs() {
	while(!q.empty() && check) {
		int t = q.front(); q.pop();
		rep(i, 0, (int)tree[t].size()) {
			int u = tree[t][i];
			if(range[u].second < range[t].first - 1 || range[u].first > range[t].second + 1) {
				check = 0;
				break;
			}
			if(range[u].second > range[t].second + 1 && range[u].first < range[t].first - 1) {
				range[u].second = range[t].second + 1;
				range[u].first = range[t].first - 1;
				q.push(u);
				continue;
			}
			if(range[u].second <= range[t].second + 1 && range[u].first >= range[t].first - 1) {
				continue;
			}
			range[u].first = max(range[t].first - 1, range[u].first);
			range[u].second = min(range[t].second + 1, range[u].second);
			q.push(u);
		}
	}
}
 
signed main() {
	fastio;
	int n, m, a, b; cin >> n;
	rep(i, 0, n - 1) {
		cin >> a >> b;
		a--; b--;
		tree[a].pb(b); tree[b].pb(a);
		range[i].first = -1000000000; range[i].second = 1000000000;
	}
	range[n - 1].first = -1000000000; range[n - 1].second = 1000000000;
	cin >> m;
	while(m--) {
		cin >> a >> b;
		a--;
		range[a] = mp(b, b);
		q.push(a);
	}
	check = 1; bfs();
	rep(i, 1, n + 1) {
		for(auto x : tree[i]) {
			if(abs(range[i].first - range[x].first) != 1) {
				return cout << "No\n", 0;
			}
		}
	}
	if(!check) return cout << "No\n", 0;
	cout << "Yes\n";
	rep(i, 0, n) {
		cout << range[i].first << "\n";
	}
}

Measured memory_bytes: 10140
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
int main(){
	cin>>n>>x>>y;
	int maxx=min(x,y);
	int minn;
	if(x+y>n) {
		minn=x+y-n;
	}
	else minn=0;
	cout<<maxx<<" "<<minn<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  string s;
  cin >> s;
  int n = s.size(), cnt = 0;
  for (int i = s.size() - 1 ; i >= 0 ; -- i) {
    if (s[i] == 'S') {
      if (!cnt) continue;
      n -= 2;
      --cnt;
    }
    else {
      ++cnt;
    }
  }
  cout << n;
}

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

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

vector<vector<int> > v(100010);
vector<int> deg(100010);
int dp[100010];

int main(){
	int n, m, x, y;
	scanf("%d%d", &n, &m);
	for(int i=0; i < m; i++) {
		scanf("%d%d", &x, &y);
		v.at(x-1).push_back(y-1);
		deg.at(y-1)++;
	}
	queue<int> que;
	for(int i=0; i < n; i++) if(deg.at(i) == 0) que.push(i);
	while(!que.empty()) {
		int ver = que.front();  que.pop();
		for(auto next: v[ver]) {
			if(--deg.at(next) == 0)
				que.push(next);
			chmax(dp[next], dp[ver]+1);
		}
	}

	int ans = 0;
	for(int i=0; i < n; i++)
		chmax(ans, dp[i]);
	printf("%d\n", ans);
}


Measured memory_bytes: 6528
#include"stdio.h"
int main()
{
    int n;
    int p;
    int i,j;
    int max;
    int min;
    int nextmin;
    scanf("%d",&n);
    scanf("%d",&min);
    scanf("%d",&p);
    max=p-min;
    if(min>p)min=p;
    for(i=2;i<n;i++)
    {
        scanf("%d",&p);
        if(min>p)
        {
            min=p;
        }
        else if(max<p-min)max=p-min;
    }
    printf("%d\n",max);
    return 0;
}


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

int main(){
    long long a, b;
    cin >> a >> b;

    long long ans = 0;
    long long tmp = 2;
    a--;
    for(long long i = 0;i < 60;i++){
        long long t1 = (b/tmp) * (tmp/2);
        if(b % tmp >= (tmp / 2)) t1+=(b%tmp)-(tmp/2)+1;
        long long t2 = (a/tmp) * (tmp/2);
        if(a % tmp >= (tmp / 2)) t2+=(a%tmp)-(tmp/2)+1;
        if((t1-t2) % 2) ans |= (1ll << i);
        tmp *= 2;
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
	int w,n,a,b,ans[30];
	cin>>w>>n;
	for(int i=1;i<=w;i++){
		ans[i]=i;
	}
	for(int i=0;i<n;i++){
		scanf("%d,%d",&a,&b);
		swap(ans[a],ans[b]);
	}
	for(int i=1;i<=w;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
#define init(c) memset(c,0,sizeof c)
#define S second
#define F first
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=20000005;
int n,k,x,t,a,b,m;
string s;
vi v;
int main(){

	cin >> n;
	set<string>st;
	while(n--){
		cin >> s;
		st.insert(s);
	}
	cout << st.size();

	
	return 0;
}

Measured memory_bytes: 19164
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int w, a, b;
    cin >> w >> a >> b;
    if ((a + w >= b && a < b + w) || (a <= b + w && b < a + w))
    {
        cout << 0 << endl;
        return 0;
    }
    if (a + w < b)
    {
        cout << b - (a + w);
    }
    else
    {
        cout << a - (b + w);
    }
}

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

///////////////////////////////////////////
const long long int INF = 1000000000000000000LL;
using ll = long long int;
using vi = vector<int>;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return 1; } return 0; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return 1; } return 0; }
template<class T>T sqar(T x){ return x*x; }
///////////////////////////////////////////

class union_find{//rank無しunion_find木
    int par[100000]={0};
public:
    union_find(int num){ for(int i=0;i<num;i++)par[i]=i; }
    int root(int x){//再帰
        if(par[x]==x){
            return x;
        }else{
            return par[x] = root(par[x]);
        }
    }
    bool same(int x,int y){ return root(x)==root(y); }//同じunionにいるか？
    void unite(int x,int y){//unionの結合
        x = root(x);y = root(y);
        if(x==y)return ;
        par[x]=y;
    }
};

int main(){
    int n,m;
    int box[100000]={0};
    cin>>n>>m;
    union_find U(n);
    rep(i,n)cin>>box[i];
    int x,y;
    rep(i,m){
        cin>>x>>y;
        U.unite(x,y);
    }
    int ans = 0;
    rep(i,n){
        if(U.same(i+1,box[i]) || box[i]==i+1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}
















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

int main() {
  int N; cin >> N;
  int A[N]; for (int i = 0; i < N; ++i) cin >> A[i];
  int seqState = 0, prevNum = A[0], seqNum = 1, seqLen = 1;
  for (int i = 1; i < N; ++i) {
    if (seqState == 0) {if (A[i] > prevNum) seqState = 1;
      else if (A[i] < prevNum) seqState = 2;
      ++seqLen;
    } else if (seqState == 1) {
      if (A[i] >= prevNum) ++seqLen;
      else {
        seqState = 0;
        ++seqNum;
        seqLen = 1;
      }
    } else if (seqState == 2) {
      if (A[i] <= prevNum) ++seqLen;
      else {
        seqState = 0;
        ++seqNum;
        seqLen = 1;
      }
    }
    prevNum = A[i];
  }
  cout << seqNum << endl;
}

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

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

int main(void)
{
    unsigned long long sum=0;
    string n;
    cin >> n;
    ll i=0;
    while(n.size()>i)
    {
        char kazu=n[i];
        sum+=int(kazu)-48;
        i++;
    }
    //cout << sum << endl;
    bool judge=false;
    if(sum%9==0)
    {
        judge=true;
    }
    if(judge)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3724
N,D =(int(x) for x in input().split())
xy = [map(int,input().split()) for _ in range(N)]
x,y = [list(i) for i in zip(*xy)]
n = 0
 
for i in range(N):
  if(x[i]**2 + y[i]**2 <= D**2):
    n += 1
 
print(n)

Measured memory_bytes: 116728
/*
	?§£????????????:Area of Polygon
	(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079)

	-status:null(????????????????????±??????????????????...)

	-comment:
        ????????????????????????
*/
var log = console.log;
if (typeof process != "undefined") {
    var input = "";
    process.stdin.resume();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', function(chunk) {
        input += chunk;
    });
    process.stdin.on('end', function() {
        var lines = input.split("\n");
        main(lines);
    });
}


function main(lines) {
    lines = lines.map(function(line) {
        return line.split(" ").filter(function(e) {
            return e != "";
        }).map(function(e) {
            var n = Number(e);
            if (n.toString() == "NaN") {
                return e.replace(/(\r)|(\n)/g, "");
            }
            return n;
        });
    });
    var last = lines.pop();
    if (last.length == 8) {
        lines.push(last);
    }
    //log(lines);
    //log(Math.pow(0.1, 10));
    //lines.shift();
    while (lines.length > 0) {
        var dataset = lines.shift();
        p_set(dataset);
    }
}

function p_set(ps) {
    var va = [ps[0] - ps[6], ps[1] - ps[7]];
    var vb = [ps[2] - ps[6], ps[3] - ps[7]];
    var vc = [ps[4] - ps[6], ps[5] - ps[7]];
    var s1 = sign_s_main(va, vb) > 0 ? 1 : -1;
    var s2 = sign_s_main(vb, vc) > 0 ? 1 : -1;
    var s3 = sign_s_main(vc, va) > 0 ? 1 : -1;
    if (
        s1 == s2 &&
        s2 == s3 &&
        s3 == s1
    ) {
        log("YES");
    } else {
        log("NO");
    }
}

function sign_s_main(pa, pb) {
    //?????????2??§????????????
    return (pa[0] * pb[1] - pa[1] * pb[0]);
}

Measured memory_bytes: 16224
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var s string
	fmt.Scan(&s)

	ans := 999
	for i := 0; i < len(s)-2; i++ {
		n, _ := strconv.Atoi(s[i : i+3])
		if d := abs(753 - n); d < ans {
			ans = d
		}
	}
	fmt.Println(ans)
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


Measured memory_bytes: 512
//#include "stdc++.h"
#include<bits/stdc++.h>
#include<iostream>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define endl "\n"
#define int long long int
inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p*p)%m;if(n%2) return (p*a)%m;else return p;}
const ll MOD = 1000000007;
const ll MOD1=1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
/*
 shuffle(x,x+n,rng) // shuffling elements of x in random order
 */

int32_t main()
{
    IOS;
    int n,k;
    cin>>n>>k;int ans=0;
    string s;
    cin>>s;
    if(k>=n-1)
    {
        ans=n-1;
    }
    else
    {
        vector<char>v;
        for(int i=1;i<n;i++)
            if(s[i]==s[i-1])
                ans++;
        for(int i=0;i<n-1;i++)
        {
            if(s[i]!=s[i+1])
                v.pb(s[i]);
        }
        v.pb(s[n-1]);
        int n1=v.size();
        int th=n1/2;
        if(k>=(th))
        {
            ans=n-1;
        }
        else
        {
            int ans1=ans,k1=k,mx;
            for(int i=1;i<n1;i+=2)
            {
                if(k1>0)
                {
                if(i==n1-1)
                    ans+=1;
                else
                    ans+=2;
                    k1--;
                }
            }
            mx=ans;
            ans=ans1;
            k1=k;
            for(int i=2;i<n1;i+=2)
            {
                if(k1>0)
                {
                    if(i==n1-1)
                        ans+=1;
                    else
                        ans+=2;
                    k1--;
                }
            }
            if(k1)
                ans++;
            ans=max(ans,mx);
        }
        
    }
    cout<<ans<<endl;
    return 0;
}


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

int main(){
    int n,q ;cin >> n >> q;
    atcoder::dsu uf(n);
    int t,u,v;
    for(int i=0;i<q; i++){
        cin >> t >> u >> v;
        if(t)cout << uf.same(u,v) << endl;
        else uf.merge(u, v);
    }
}

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

using namespace std;

typedef long long int ll;

const int N = 21;
const int mod = (int) 1e9 + 7;

int n;
int mat[N][N];
int memo[N][1 << N];

int dp(int at, int mask) {
    if(at == n) return 1;
    int &ans = memo[at][mask];
    if(ans != -1) return ans;
    ans = 0;
    for(int i = 0; i < n; ++i) {
        if((mask & (1 << i)) > 0) continue;
        if(mat[at][i] == 0) continue;
        ans += dp(at + 1, mask | (1 << i));
        ans %= mod;
    }
    return ans;
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> mat[i][j];
        }
    }
    memset(memo, -1, sizeof(memo));
    cout << dp(0, 0) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;
    solve();
    return 0;
}

Measured memory_bytes: 172288
fn bishop() -> Result<i64, &'static str> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .map_err(|_| "input error")?;
    let hw :Vec<i64> = input.trim_right().split_whitespace().
        map(|s| s.parse::<i64>().unwrap()).collect();

    if hw[0] == 1 || hw[1] == 1 {
        Ok(1)
    }
    else {
        Ok(hw[0] * (hw[1] / 2) + ((hw[0] / 2 + hw[0] % 2) * (hw[1] % 2)))
    }
}

fn main() {
    println!("{}", bishop().unwrap());
}

Measured memory_bytes: 4352
/*
By Tianyi Chen. All rights reserved.
Date: 2016-07-31
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
bool can[100001];int cnt[100001];
int main() {
 scanf("%d%d",&n,&m);can[1]=1;fill(cnt+1,cnt+1+n,1);
 while (m--) {
  scanf("%d%d",&x,&y);
  can[y]|=can[x];++cnt[y];--cnt[x];
  if (cnt[x]==0&&can[x])can[x]=0;
 }
 printf("%d\n",accumulate(can+1,can+1+n,0));
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
int main() {
  
  int N;
  cin >> N;
  int sum = 0;
  
  vector<int> cont(N);
  
  for(int i = 0 ; i < N ; i++){
    
    cin >> cont.at(i);
    
  }
  
  for(int i = 1 ; i < N - 1 ; i++){
    
    if( ( (cont.at(i) > cont.at(i+1) ) && ( cont.at(i) < cont.at(i-1) ) ) || ( (cont.at(i) < cont.at(i+1) ) && ( cont.at(i) > cont.at(i-1) ) ) ){
      
      sum++;
    }
  }
  
  cout << sum << endl;
}

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

int prime(int x) {
	for (int i=2; i<x/2; i++)
      if (x%i == 0) return 0;
  	return 1;
}

int main() {
	int x; cin >> x;
  	while(!prime(x)) {
    	x++;
    }
  	cout << x << '\n';
	return 0;
}


Measured memory_bytes: 256
import math
N = int(input())

def factrize(N):
    L={}
    for n in range(2,N+1):
        L[n]=0
        while N % n == 0:
            L[n]+=1
            N = N/n
    return L

f_ = {}
for n in range(2,int(N)+1):
    f_[n]=0
        
for n in range(1,N+1):
    F=factrize(n)
    for f in F.keys():
        f_[f]+=F[f]
        
ans=1
for f in f_.keys():
    if f_[f] != 0:
        ans=ans*(f_[f]+1)
        
print(ans%((10**9)+7))

Measured memory_bytes: 9196
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::pair<long long, long long> pll;

using namespace std;

const long long mod = 1000000007;

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

	string s;
	cin >> s;

	int ans = 0;
	int now = 0;
	rep(i, s.length()) {
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') ++now;
		else now = 0;

		ans = max(now, ans);
	}

	cout << ans << "\n";

	return 0;
}


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

template<typename ... Ts> void read(Ts& ...vs){(std::cin >> ... >> vs);}
template<typename T> void write(const T& v){std::cout << v << std::endl;}

int main()
{
    std::size_t K;
    read(K);

    std::vector<std::uint64_t> lunlun{1,2,3,4,5,6,7,8,9};

    std::size_t prev_begin = 0;
    std::size_t prev_end   = lunlun.size();
    while(lunlun.size() <= K)
    {
        for(std::size_t i=prev_begin; i<prev_end; ++i)
        {
            const std::uint64_t lun = lunlun.at(i);
            std::string s = std::to_string(lun);
            const std::uint64_t last_digit = s.back() - '0';

            if(last_digit != 0)
            {
                lunlun.push_back(std::stoull(s + std::to_string(last_digit - 1)));
            }
            lunlun.push_back(std::stoull(s + std::to_string(last_digit)));
            if(last_digit != 9)
            {
                lunlun.push_back(std::stoull(s + std::to_string(last_digit + 1)));
            }
        }
        prev_begin = prev_end;
        prev_end   = lunlun.size();
    }

    std::sort(lunlun.begin(), lunlun.end());

    std::cout << lunlun.at(K-1) << std::endl;
    return 0;
}


Measured memory_bytes: 5768
n = int(input())
s1 = input()
s2 = input()
max = 1000000007

ans = 1
pt = 0
beforestate = 0 
if s1[0] == s2[0]:
    ans = 3
    pt = 1
    beforestate = 0 #tate
else :
    ans = 6
    pt = 2
    beforestate = 1 #yoko

while pt < n:
    if beforestate == 0 and s1[pt] == s2[pt]:
        ans = ans * 2 % max
        beforestate = 0
        pt += 1
    elif beforestate == 1 and s1[pt] == s2[pt]:
        beforestate = 0
        pt += 1
    elif beforestate == 0 and s1[pt] != s2[pt]:
        ans = ans * 2 % max
        beforestate = 1
        pt += 2
    elif beforestate == 1 and s1[pt] != s2[pt]:
        ans = ans * 3 % max
        beforestate = 1
        pt += 2

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int N = 2e5+5;
const dd eps = 1e-5;
const ll mod = 1e9+7;

const int MAXN = 100010;
 
string now;
ll ans,dp[N][2];
int main(){
  // freopen("input.txt","r",stdin);
  cin>>now;
  now = "0" + now;
  for(int i = now.size()-1;i >= 0;i--){
    int num = now[i] - '0';
    if(num < 5){
      ans += num;
      continue;
    }
    if(5 < num){
      now[i-1]++;
      ans += 10-num;
      continue;
    }
    if(now[i-1]-'0' >= 5) now[i-1]++;
    ans += num;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 2308
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    long long a,b;
    cin >> a >> b;
    //a-k=k-b;
    if((a+b)%2==0){
        cout << (a+b)/2 << endl;
    }else {
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
use std::collections::{BinaryHeap, HashMap};
use std::io::Read;



fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: i32 = iter.next().unwrap().parse().unwrap();
    let m: i32 = iter.next().unwrap().parse().unwrap();
    let mut jobs:HashMap<i32, Vec<i32> > = HashMap::new();
    let mut available_jobs:BinaryHeap<i32> = BinaryHeap::new();
    
    for _ in 0..n{    
        let a:i32 = iter.next().unwrap().parse().unwrap();
        let b:i32 = iter.next().unwrap().parse().unwrap();
        let etry = jobs.entry(a).or_insert(vec![]);
        etry.push(b);
    }

    let mut ans = 0i32;
    for day in 1..m+1{
        let entr = jobs.entry(day).or_insert(vec![]);
        for j in entr{
            available_jobs.push(*j);
        }
        if let Some(&x) = available_jobs.peek(){
            ans += x;
            available_jobs.pop();
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 20408
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(long.Parse).OrderBy(x => x).ToArray();
            Console.WriteLine(input[1] - input[0] + input[2] - input[1]);
        }
    }
}

Measured memory_bytes: 13396
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

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

int ice[90][90];
int ans,m,n;
void dfs(int x,int y,int num){
  ans=max(num,ans);
  rep(i,4){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0 || nx>=m || ny<0 || ny>=n || ice[nx][ny]==0)continue;
    ice[nx][ny]=0;
    dfs(nx,ny,num+1);
    ice[nx][ny]=1;
  }
}


main(){
  while(cin>>m>>n,m|n){
    ans=0;
    rep(i,n)rep(j,m)cin>>ice[j][i];

    rep(i,n)rep(j,m){
      if(ice[j][i]){
        ice[j][i]=0;
        dfs(j,i,1);
        ice[j][i]=1;
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 0
def find(x):
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x

def same(x, y):
  return find(x) == find(y)

 
def size(x):
  return-par[find(x)]

n, m, k = map(int, input().split())

par = [-1]*n
FF = [0] * n
BB = [[] for i in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  FF[a-1] += 1
  FF[b-1] += 1
for i in range(k):
  a, b = map(int, input().split())
  BB[a-1].append(b-1)
  BB[b-1].append(a-1)
result = []

for i in range(n):
  ans = size(i) - FF[i] -1
  for j in BB[i]:
    if same(i, j):
      ans -= 1
  result.append(ans)
  
print(*result)

Measured memory_bytes: 28748
#include<bits/stdc++.h>
using namespace std ;
int main()
{
    char a ;
    cin >> a ;
    if(a=='a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
        cout << "vowel" << endl ;
    else cout << "consonant" << endl ;
}


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

int main(){
    string s;
    cin>>s;
    int n = s.size();
    vector<int> next(n);
    for(int i = 0 ; i < n ; ++i){
        if(s[i] == 'R')next[i] = i + 1;
        else next[i] = i - 1;
    }
    for(int t = 0 ; t < 100 ; ++t){
        vector<int> nn(n);
        for(int i = 0 ; i < n ; ++i){
            nn[i] = next[next[i]];
        }
        nn.swap(next);
    }
    vector<int> ans(n);
    for(int i = 0 ; i < n ; ++i){
        ans[next[i]]++;
    }
    for(int i = 0 ; i < n ; ++i){
        cout<<ans[i]<<" ";
    }
    return 0;
}


Measured memory_bytes: 1520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5+10;
int n;
int main() {
   //  freopen("test.txt","r",stdin);
    int n,k;
    int a[maxn];
    ll ans=0;
    cin>>k>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        ans+=a[i];
    }
    if(ans>=k) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

/*
1.变量范围经常搞错，也就是临界情况不清晰
  1.1 加上一点，诸如下标从0~n-1的情况，对于某个其中的值，经常搞错个数和下标
2.经常性读错题目，尤其是看英文题面的情况下
3.结合上一点，如果是英文题面，一定要英文，只准翻译单个单词，逼着自己看英文题面
4.for循环中的i爆LL可能很难注意到
5.千万不要忽视轻视简单的问题
*/





Measured memory_bytes: 640
#define FNAME ""

#include <bits/stdc++.h>

#define hash padjf9srpi
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define forn(i, n) for (int i = 0; i < (n); i++)
#define fornr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define forab(i, a, b) for (int i = (a); i < (b); i++)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
 
#ifdef _WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;                                                                                                                                                                                      
typedef vector <int> vi;

template <class T> T sqr(const T &a) {return a * a;}

int a[200000];


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

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

    int n, c, k;
    scanf("%d%d%d", &n, &c, &k);
    int lst, pos = 0;

    int ans = 0;
    forn(i, n) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    forn(i, n) {
        if (!i) pos = 0, lst = a[i];
        if (i - pos == c || a[i] - lst > k) {
            ans++;
            pos = i;
            lst = a[i];
        }
    }
    ans++;
    printf("%d\n", ans);
}




Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

type drink struct {
	A, B int
}
type drinkList []drink

func (a drinkList) Len() int           { return len(a) }
func (a drinkList) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a drinkList) Less(i, j int) bool { return a[i].A < a[j].A }

func main() {
	sc.Split(bufio.ScanWords)

	N, M := scanInt(), scanInt()
	L := make(drinkList, N)
	for i := 0; i < N; i++ {
		L[i].A, L[i].B = scanInt(), scanInt()
	}
	sort.Sort(L)

	ans := 0
	for _, l := range L {
		if l.B <= M {
			ans += l.A * l.B
			M -= l.B
		} else {
			ans += l.A * M
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 3840
import java.awt.Point;
import java.util.ArrayList;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
 enum Vec {
	R,
	U,
	L,
	D;
	Vec next() {
	 return (this == R) ? D : (this == D) ? L
		 : (this == L) ? U : R;
	}
 }

 public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	boolean isKisu = true;
	List<boolean[]> gusu = new ArrayList<boolean[]>();
	List<boolean[]> kisu = new ArrayList<boolean[]>();
	while (in.hasNextLine()) {

	 isKisu = !isKisu;
	 char[] str = in.nextLine().toCharArray();
	 boolean[] bs = new boolean[str.length];
	 for (int i = 0; i < bs.length; i++) {
		bs[i] = (str[i] == '1');
	 }
	 ((isKisu) ? kisu : gusu).add(bs);
	}
	Map<Point, Map<Vec, Point>> map = new HashMap<Point, Map<Vec, Point>>();
	int ySize = gusu.size();
	int xSize = kisu.get(0).length;
	for (int y = 0; y < ySize; y++) {
	 for (int x = 0; x < xSize; x++) {
		map.put(
		  new Point(x, y),
		  new EnumMap<Vec, Point>(Vec.class));
	 }
	}
	{
	 int size = gusu.size();
	 for (int y = 0; y < size; y++) {
		int length = gusu.get(y).length;
		for (int x = 0; x < length; x++) {
		 if (gusu.get(y)[x]) {
			Point o = new Point(x, y);
			Point r = new Point(x + 1, y);
			map.get(o).put(Vec.R, r);
			map.get(r).put(Vec.L, o);
		 }
		}
	 }
	}
	{
	 int size = kisu.size();
	 for (int y = 0; y < size; y++) {
		int length = kisu.get(y).length;
		for (int x = 0; x < length; x++) {
		 if (kisu.get(y)[x]) {
			Point o = new Point(x, y);
			Point d = new Point(x, y + 1);
			map.get(o).put(Vec.D, d);
			map.get(d).put(Vec.U, o);
		 }
		}
	 }
	}
	Vec next = Vec.R;
	Point posi = new Point(0, 0);
	do {
	 next = next.next().next().next();
	 Map<Vec, Point> point = map.get(posi);
	 while (!point.containsKey(next)) {
		next = next.next();
	 }
	 System.out.print(next);
	 posi = point.get(next);
	} while (posi.x != 0 || posi.y != 0);
	System.out.println();
 }
}

Measured memory_bytes: 12000
use std::cmp::*;
use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::io::*;
use std::str::FromStr;
use std::string::String;

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

    token.parse().ok().expect("failed to parse token")
}

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}

struct DP {
    w: Vec<i32>,
    memo: Vec<Vec<i32>>,
}

impl DP {
    fn new(n: usize, w: Vec<i32>) -> Self {
        DP {
            w: w,
            memo: vec![vec![-1; n + 10]; n + 10],
        }
    }

    fn dfs(&mut self, l: usize, r: usize) -> i32 {
        if self.memo[l][r] != -1 {
            return self.memo[l][r];
        }

        if r - l <= 1 {
            return 0;
        }

        let mut res = 0i32;

        if (self.w[l] - self.w[r - 1]).abs() <= 1 && self.dfs(l + 1, r - 1) == (r - l - 2) as i32 {
            res = (r - l) as i32;
        }

        for mid in l + 1..r {
            res = max(res, self.dfs(l, mid) + self.dfs(mid, r));
        }

        self.memo[l][r] = res;

        return self.memo[l][r];
    }
}

fn main() {
    loop {
        let n: usize = read();
        if n == 0 {
            return;
        }

        let w: Vec<i32> = (0..n).map(|_| read()).collect();
        let mut dp = DP::new(n, w);

        dp.dfs(0, n);

        println!("{}", dp.memo[0][n]);
    }
}



Measured memory_bytes: 5064
import java.io.*;
import java.util.*;
 
public class Main {
  private static boolean debug = false;
  private static boolean elapsed = false;
 
  private static PrintWriter _err = new PrintWriter(System.err);
 
  private void solve(Scanner sc, PrintWriter out) {
    String s1 = sc.next();
    String s2 = sc.next();
    String s3 = sc.next();
 
    out.println("" + s1.charAt(0) + s2.charAt(0) + s3.charAt(0));
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();
 
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();
 
    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 21844
class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)

def main():
    n,q = map(int,input().split())
    uf = UF(n)
    for _ in range(q):
        ope,x,y = map(int,input().split())
        if ope == 0:
            uf.union(x,y)
        else:
            print(1 if uf.is_same(x,y) else 0)

if __name__ == "__main__":
    main()



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

typedef long long ll;

const int nmax=110;
const int wmax=100010;

ll val[nmax];
int w[nmax];
ll dp[nmax][wmax];

ll rec(int n , int p)
{
    if(n==0 || p==0)return 0;
    if(dp[n][p]!=-1)return dp[n][p];

    if(p - w[n]>=0){
    dp[n][p]=max(rec(n-1,p),rec(n-1,p-w[n])+val[n]);
    }
    else dp[n][p]=rec(n-1,p);
    return dp[n][p];
}

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

    int n,tot;cin>>n>>tot;
    for(int i=1;i<=n;++i)cin>>w[i]>>val[i];
    for(int i=0;i<nmax;++i)
    {
        for(int j=0;j<wmax;++j)dp[i][j]=-1;
    }

    cout<<rec(n,tot);

    return 0;
}


Measured memory_bytes: 86272
h, w = gets.split.map(&:to_i)

lines = []
h.times do
  line = gets.chomp
  lines << line
end

dim = [[0, 1], [1, 0], [0, -1], [-1, 0]]

lines.each_with_index do |l, i|
  0.upto(w-1) do |j|
    next if l[j] == '.'
    flag = false

    dim.each do |pos|
      dx = j + pos[0]
      dy = i + pos[1]
      next if (dx >= w || dy >= h) || (dx < 0 || dy < 0)
      flag = true if lines[dy][dx] == '#'
      break if flag
    end

    unless flag
      puts 'No'
      exit
    end

  end
end

puts 'Yes'


Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>

#define ll long long
#define vl vector<ll>
#define vvl vector< vector<ll> >
#define vb vector<bool>
#define vbb vector< vector<bool> >
#define vs vector<string>
#define vc vector<char>
#define vvc vector< vector<char> >

#define all(a) (a).begin(),(a).end()
using namespace std;

bool check(string s,char c, ll v, ll e){
	for (int i = v; i < e; ++i){
		if (s[i] == c) return 1;
	}return 0;
}

ll count(string s, ll cut){
	ll ret = 0;
	for (char i = 'a'; i <= 'z'; ++i){
		if (check(s, i, 0, cut) && check(s, i, cut, s.size())){
			ret++;
		}
	}return ret;
}

int main(){
	ll n; cin >> n;
	string s; cin >> s;
	ll ans = 0;
	for (int i = 0; i < n; ++i){
		ans = max(ans, count(s, i));
	}cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256