akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int cnt[MAXN];
int main()
{
    int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	for(int i = 1; i < n; ++i){
		if(s[i-1] == 'A' && s[i] == 'C')	cnt[i+1] = cnt[i] + 1;
		else	cnt[i+1] = cnt[i];
		//cout <<  cnt[i+1] << endl;
	}
	int l, r;
	while(q--){
		cin >> l >> r;
		cout << (cnt[r]-cnt[l]) << endl;
	}
	return 0;
}




Measured memory_bytes: 1408
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a;
    string b;
    int A=0,W=0,T=0,R=0;
    cin>>a;
    for(int z=0;z<a;z++){
        cin>>b;
        if(b=="AC"){
            A++;
        }else if(b=="WA"){
            W++;
        }else if(b=="TLE"){
            T++;
        }else{
            R++;
        }
    }
    //cout<<A<<" "<<W<<" "<<T<<" "<<R<<endl;
    cout<<"AC x "<<A<<endl;
    cout<<"WA x "<<W<<endl;
    cout<<"TLE x "<<T<<endl;
    cout<<"RE x "<<R<<endl;
}

Measured memory_bytes: 3596
#include <algorithm>
#include <iostream>
#include <queue>
#define N_MAX 30
#define INF (1e9)
using namespace std;
void dijkstra();
int w,h,data[N_MAX][N_MAX],d[N_MAX][N_MAX][4],c[4];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
typedef struct stu{
  int mincost,y,x,dir;
  bool operator<(const stu & right)const{
    return mincost>right.mincost;
  }
} dat;

int main(){
  while(1){
    cin>>w>>h;
    if(!w&&!h) break;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++) cin>>data[i][j];
    for(int i=0;i<4;i++) cin>>c[i];
    dijkstra();
  }
  return 0;
}

void dijkstra(){
  priority_queue<dat > Q;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      for(int k=0;k<4;k++) d[i][j][k]=INF;
  d[0][0][1]=0;
  Q.push((dat){0,0,0,1});
  while(!Q.empty()){
    dat t=Q.top(); Q.pop();
    int cost=t.mincost,y=t.y,x=t.x,dir=t.dir;
    if(cost>d[y][x][dir]) continue;
    for(int i=0;i<4;i++){
      int ny=y+dy[(dir+i)%4],nx=x+dx[(dir+i)%4],ndir=(dir+i)%4;
      if(ny<0||nx<0||h<=ny||w<=nx) continue;
      int *ncost=&d[ny][nx][ndir];
      if(*ncost>cost+c[i]) *ncost=cost+c[i],Q.push((dat){*ncost,ny,nx,ndir});
      if(data[y][x]!=i) continue;
      if(*ncost>cost) *ncost=cost,Q.push((dat){*ncost,ny,nx,ndir});
    }
  }
  cout<<min(d[h-1][w-1][1],d[h-1][w-1][2])<<endl;
}

Measured memory_bytes: 1360
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int h, w, a, b;

int main() {
	cin >> h >> w >> a >> b;
	
	inc(i, h) {
	inc(j, w) {
		cout << ((i < b) == (j < a) ? 0 : 1);
	} cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int N, K;
int cnt[100100];

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> K;
    rep(i, N) {
        int a, b; cin >> a >> b;
        cnt[a] += b;
    }
    int acc = 0;
    rep(i, 100100) {
        acc += cnt[i];
        if (acc>=K) {
            cout << i << endl;
            exit(0);
        }
    }
}

Measured memory_bytes: 1024
//{{{
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printw) FUNC(printwe) FUNC(printb) FUNC(printbe) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    string s2;
    for(auto& c : s){
        if(s2.empty() || s2.back() == c){
            s2 += c;
        }else{
            s2.pop_back();
        }
    }
    cout << s.size() - s2.size() << '\n';
}


Measured memory_bytes: 704
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
using ll = long long int;
using pi=pair<int,int>;
using vi = vector<int>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

constexpr int INF = 1 << 30;  // 1e9
constexpr ll INFL = 1l << 60; // 1e18
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define RANGE(i, a, b) for (int i = (a); i <= (b); i++)
#define RANGER(i, a, b) for (int i = (b); i >= (a); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, 0, (n))

#define EVAL 1

#ifdef EVAL
#define LOG(x) ;
#else
#define LOG(x) cerr << #x << ": " << (x) << endl;
#endif

vpi A=vpi(2e5);
int N;
void solve() {
	cin>>N;
	REP(i,N) {
		A[i].first=i;
		scanf("%d", &A[i].second);
	}
	sort(&A[0],&A[N],[](auto& a, auto& b){return a.second<b.second;});
	int ans=0,ln=0,pvi=INF;
	REP(i,N){
		if(pvi<A[i].first){
			ln++;
		}else{
			ln=1;
		}
		pvi=A[i].first;
		ans=max(ans,ln);
		LOG(ln)
	}
	cout<<N-ans<<endl;
	//*
	REP(i,N){
		LOG(A[i].first);
		LOG(A[i].second);
	}
	//*/
}

int main() {
	solve();
	return 0;
}

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

using namespace std;
typedef long long int lli;
lli n,c;
vector <lli> weight(105);
vector <lli> value(105);
lli dp[105][100005];
lli knap(lli i,lli c);

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>c;
	for (int i=0;i<n;i++){
		cin>>weight[i]>>value[i];
	}
	for (int i=0;i<n+1;i++){
		for (int j=0;j<c+2;j++) dp[i][j]=-1;
	}
	knap(0,c);
	cout<<dp[0][c]<<endl;
	
	return 0;
}

lli knap(lli i,lli c){
	if (i==n) return 0;
	if (dp[i][c]!=-1) return dp[i][c];
	if (c>=weight[i]){
		dp[i][c]=max(knap(i+1,c-weight[i])+value[i],knap(i+1,c));
	}
	else dp[i][c]=max(knap(i+1,c),dp[i][c]);
	return dp[i][c];
}

Measured memory_bytes: 80128
#include<stdio.h>                                                               
int main(void){
 
  int n,m,a[100],b[100],i,j,count;
 
  scanf("%d %d",&n,&m);
  for(i=0;i<m;i++){
    scanf("%d %d",&a[i],&b[i]);
  }
 
  count = 0;
 
  for(i=0;i<n;i++){
    count = 0;
    for(j=0;j<m;j++){
      if(a[j]==i+1){
	count = count + 1;
      }
      if(b[j]==i+1){
	count = count + 1;
      }
    }
      printf("%d\n",count);
  }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x[ohara],y,sum,pos;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll dp[100][100][50*50+100];

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>a;
    rep(i,n)cin>>x[i];
    dp[1][1][x[0]]=1;
    dp[1][0][0]=1;
    rrep(i,2,n+1){
        rep(j,n+1){
            rep(k,50*50+1){
                if(j==0||k<x[i-1]){
                    dp[i][j][k]+=dp[i-1][j][k];
                }
                else dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]+dp[i-1][j][k];
            }
        }
    }
    rep(i,n+1){
        ans+=dp[n][i][a*i];
    }
    Cout(ans-1);
    return 0;
}


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

int main()
{
  double n;
  cin >> n;
  for(double i = n;i > 0; i--){
    if(ceil(sqrt(i)) == floor(sqrt(i))) {
      cout << setprecision(10) << i << endl;
      return 0;
    }
  }
            
       
       

  return 0;
}

Measured memory_bytes: 3736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <array>
using namespace std;
typedef long long ll;
ll mod=1000000007;
ll h,w,a,b;
int uf[100000][2]={};
int fac[200005],inv[200005];
ll qpow(ll a, ll b)
{
  int ret=1;
  while(b)
    {
      if(b & 1)ret=(ll)ret * a % mod;
      a=(ll) a* a %mod;
      b >>= 1;
    }
  return ret;
}

void init()
{
  fac[0]=1;
  for(int i=1;i<200005;i++)
    {
      fac[i]=(ll)fac[i-1]*i%mod;
    }
  for(int i=0;i<200005;i++)
    {
      inv[i]=qpow(fac[i],mod-2);
    }
}
ll comb(ll n,ll m)
{
  return (ll)fac[n]*inv[m]%mod*inv[n-m] %mod;
}

int main(int argc,char const* argv[])
{
  cin >> h >> w >> a >> b;
  init();
  ll ans=0;
  for(int i=1;i<=h-a;i++)
    {
      ans=(ans+(ll)comb(i+b-2,b-1)*comb(h-i+w-b-1,h-i)%mod)%mod;
    }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1920
N, X, Y = list(map(int, input().split()))
X -= 1
Y -= 1

M = [[N] * N for _ in range(N)]


for j in range(N):
    if j > X:
        M[j][j-1] = 1
        for k in range(j-1, X-1, -1):
            M[j][k] = min(M[j][k], M[j][k+1] + 1)
        M[j][Y] = M[j][X] + 1
        for k in range(Y-1, X, -1):
            M[j][k] = min(M[j][k], M[j][k+1] + 1)

    for i in range(j+1, N):

        if j == X:
            M[j][Y] = 1
            for m in range(Y-1, X, -1):
                M[j][m] = min(M[j][m], M[j][m+1] + 1)
        if i - j == 1:
            M[j][i] = 1
        M[j][i] = min(M[j][i], M[j][i-1] + 1)
        if i == X:
            M[j][Y] = M[j][i] + 1
            for m in range(Y-1, X, -1):
                M[j][m] = min(M[j][m], M[j][m+1] + 1)

ans = [0] * N

for j in range(N):
    for i in range(j+1, N):
        ans[M[j][i]] += 1

for a in ans[1:]:
    print(a)


Measured memory_bytes: 82268
package main

import (
	"fmt"
)

var n, m, q int
var ms int
var as, bs, cs, ds []int

func main() {
	fmt.Scan(&n, &m, &q)
	as = make([]int, q)
	bs = make([]int, q)
	cs = make([]int, q)
	ds = make([]int, q)
	for i := range as {
		fmt.Scan(&as[i], &bs[i], &cs[i], &ds[i])
	}
	for i := 1; i <= m; i++ {
		loop([]int{i})
	}
	fmt.Println(ms)
}

func loop(ns []int) {
	num := len(ns)
	last := ns[num-1]
	for i := last; i <= m; i++ {
		nns := make([]int, num+1)
		copy(nns, ns)
		nns[num] = i
		if num == n-1 {
			score := calc(nns)
			ms = max(ms, score)
		} else {
			loop(nns)
		}
	}
}

func calc(s []int) int {
	var sum int
	for i := range as {
		if s[bs[i]-1]-s[as[i]-1] == cs[i] {
			sum += ds[i]
		}
	}
	return sum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1005;
const int MOD = (int)1e9 + 7;
int A[N];
int B[N];

bool col[N];
bool row[N];

vector<pii> T[N*N];

int main(){
  fastIO;
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i ++ ){
    cin >> A[i];
    T[A[i]].push_back(mp(i,1));
  }
  for(int i = 1; i <= m ; i ++ ){
    cin >> B[i];
    T[B[i]].push_back(mp(i,2));
  }
  for(int i = 1; i <= n * m ; i ++ ){
    if(T[i].size() >= 3){
      cout << 0;
      return 0;
    }
    if(T[i].size() == 2){
      if(T[i][0].se == T[i][1].se){
        cout << 0;
        return 0;
      }
    }
  }
  int ans = 1;
  int lar = 0;
  int cl = 0, rw = 0;
  for(int i = n * m ; i >= 1; i -- ){
    if(T[i].size() == 0){
      ans = (ans * 1ll * max(0,cl * rw - lar)) % MOD;
    }
    else if(T[i].size() == 1){
      if(T[i][0].se == 1){
        if(col[T[i][0].fi] == false) cl ++ ;
        ans = (ans * 1ll * rw) % MOD;
      }
      else{
        if(row[T[i][0].fi] == false) rw ++ ;
        ans = (ans * 1ll * cl) % MOD;
      }
    }
    else{
      if(T[i][0].se == 1){
        if(col[T[i][0].fi] == false) cl ++ ;
      }
      else{
        if(row[T[i][0].fi] == false) rw ++ ;
      }
      if(T[i][1].se == 1){
        if(col[T[i][1].fi] == false) cl ++ ;
      }
      else{
        if(row[T[i][1].fi] == false) rw ++ ;
      }
      
    }
    lar ++ ;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 23936
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)

vector<int> f,s;
int main(void){
	int n;
	scanf("%d",&n);
	for(int e=0;e<n;e++){
		int x,y;
		scanf("%d%d",&x,&y);
		f.push_back(x);
		s.push_back(y);
	}
	sort(f.begin(),f.end());
	sort(s.begin(),s.end());
	if(n%2){
		printf("%d\n",s[(n/2)]-f[(n/2)]+1);
	}else{
		int ff = ((s[n/2]+s[(n/2)-1]));
		int ss = ((f[n/2]+f[(n/2)-1]));
		printf("%d\n",ff-ss+1);
	}
	return 0;
}


Measured memory_bytes: 5088
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vi vector<int>
#define f first 
#define s second 
using namespace std;
const int mod=1e9+7;
int logi(int n){int p=0;while(n/2){n=n/2;p++;}return p;}
int poww(int x,int y){int pro=1;while(y){if(y&1)pro=((pro%mod)*(x%mod)%mod);y=y>>1;x=((x%mod)*(x%mod)%mod);}return pro;}
int poww2(int x,int y){int pro=1;while(y){if(y&1)pro=pro*x;y=y>>1;x=x*x;}return pro;}
bool isprime(int n){ if(n==1) return false; for(int i=2;i<=sqrt(n);i++)	if(n%i==0) return false; return true;}

/*

*/



void solve()
{
	int n;
	cin>>n;
	vi v(n);
	map<int,int> mp;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
		mp[v[i]]++;
		sum+=v[i];
	}
	int q;
	cin>>q;
	while(q--)
	{
		int b,c;
		cin>>b>>c;
		int minus = mp[b]*b;
		int plus = mp[b]*c;
		//cout<<plus<<" "<<minus<<" ";
		sum=sum+plus-minus;
		cout<<sum<<'\n';
		mp[c]+=mp[b];
		mp[b]=0;
	}
}

int32_t main()																																	
{
	fast;
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 10064
a,b,c=map(int,input().split())
k=int(input())
for i in range(k):
  if c<=b or c <= b*2:
    c*=2
  elif b<=a or b <= a*2:
    b*=2
  else:
    a*=2
  
if a<b and b<c:
  print("Yes")
else:
  print("No")

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


int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int s1=a+b;
    int s2=c+d;
    if(s1>s2)
        cout<<"Left";
    if(s2>s1)
        cout<<"Right";
    if(s1==s2)
        cout<<"Balanced";
    return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    let w = std::io::BufWriter::new(out.lock());
    f(w);
}

#[allow(unused_macros)]
macro_rules! debug {
    ($var:expr) => {
        match &$var { v => eprintln!(concat!(stringify!($var), "={:?}"), v) }
    };
    ($var:expr, $($vars:expr),*) => {
        match &$var { v => eprint!(concat!(stringify!($var), "={:?} "), v) }
        debug!($($vars),*);
    };
}

fn main() {
    let n: usize = input();
    let s: Vec<char> = input::<String>().chars().collect();
    const MOD: i64 = 1000000007;

    let mut cnt = 1;
    let mut t = 0;
    for i in 0..s.len() {
        if s[i] == 'B' {
            if t & 1 == 0 {
                t += 1;
            } else {
                cnt *= t;
                cnt %= MOD;
                t -= 1;
            }
        } else {
            if t & 1 == 0 {
                cnt *= t;
                cnt %= MOD;
                t -= 1;
            } else {
                t += 1;
            }
        }
    }

    if t > 0 {
        println!("0");
    } else {
        for i in 1..n as i64 + 1 {
            cnt *= i;
            cnt %= MOD;
        }
        println!("{}", cnt);
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <string>
#include <sstream>

using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;

bool pairCompare(const pair<ll, ll>& firstElof, const pair<ll, ll>& secondElof)
{
    return firstElof.first < secondElof.first;
}
 

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

    ll N, M;
    cin >> N >> M;
    pair<ll, ll> AB[N];
    for (ll i = 0; i < N; ++i) {
        ll A, B;
        cin >> A >> B;
        AB[i] = make_pair(A, B);
    }

    sort(AB, AB + N, pairCompare);

    ll ans = 0;
    ll num = 0;
    for (ll i = 0; i < N; ++i) {
        ll tmp = AB[i].first * AB[i].second;
        if (num + AB[i].second < M) {
            ans += tmp;
            num += AB[i].second;
        } else {
            ans += AB[i].first * (M - num);
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define mp make_pair
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

const ll MOD=1e9+7;

ll ad(ll x,ll y=0){
  return (x+y)%MOD;
}

ll mlt(ll x,ll y=1){
  return (x*y)%MOD;
}

int main(){
  ll n,dp[110][64]={};
  int f[64]={};
  f[33]=3;//即死
  f[16]=f[20]=f[28]=f[4]=f[52]=2;//次Cで死
  f[24]=f[36]=1;//両方
  cin>>n;
  if(n==1){cout<<4<<endl;return 0;}
  if(n==2){cout<<16<<endl;return 0;}
  fr(i,4) fr(j,64) if(f[j]!=1&&f[j]!=3) dp[i][j]=1;
  for(int i=4;i<110;i++){
    fr(j,64){
      if(f[j]==1||f[j]==3) continue;
      int k=(j*4)%64,mat=j/16;
      fr(l,4){
        if(mat==2&&f[k+l]==2) continue;
        dp[i][j]=ad(dp[i][j],dp[i-1][k+l]);
      }
    }
  }
  ll ans=0;
  fr(i,64) ans=ad(ans,dp[n][i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N = int(input())
A = map(int, input().split())
MOD = 10**9 + 7

# p[n]: 最下位ビットからnビット目が1になっている数字の個数
p=[0] * 60
for a in A:
  for i in range(60):
    p[i] += (a>>i)&1

#print(p)
ans = 0
for i in range(60):
  # nビット目同士を足したときの合計
  sn = (N-p[i]) * p[i]
  ans = (ans + (sn << i)) % MOD

print(ans)


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


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

    int cnt = 1;
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(cnt == a[i]) cnt++;
        else ans++;
    }
    if(ans == n) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4048
(* Vicfred
 * https://atcoder.jp/contests/abc132/tasks/abc132_b
 * implementation
 * *)
let main = Scanf.scanf "%d\n" @@ fun n ->
    let p = Array.init n @@ fun _ -> Scanf.scanf " %d" ( + ) 0 in
    Array.init (n - 2) (fun i -> p.(i), p.(i + 1), p.(i + 2))
    |> Array.fold_left (fun v (x, y, z) -> if (x < y && y < z) || (x > y && y > z) then v + 1 else v) 0
    |> Printf.printf "%d\n"



Measured memory_bytes: 3692
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		
		if(x < 1200) {
			System.out.println("ABC");
		} else {
			System.out.println("ARC");
		}
	}
}




Measured memory_bytes: 35888
#include<bits/stdc++.h>
using namespace std;
long long n,k;
typedef struct node
{
	long long a[51][51];
	struct node operator *(const struct node & tmp)
	{
		int i,j,K;
		struct node ret;
		memset(ret.a,0,sizeof(ret.a));
		for(K=1;K<=n;K++)
		{
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
				{
					if(a[i][K]&&tmp.a[K][j])
						ret.a[i][j]=((long long)a[i][K]*tmp.a[K][j]+ret.a[i][j])%1000000007;
				}			
			}
		}
		return ret; 
	}
}NODE,*PNODE;
NODE ans,g;
int main()
{
	int flag=0,i,j;
	long long a;
	scanf("%lld %lld",&n,&k);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%lld",&g.a[i][j]);
		}
	}
	while(k)
	{
		if(k%2)
		{
			if(!flag)
			{
				ans=g;
				flag=1;
			}
			else
				ans=ans*g;
		}
		g=g*g;
		k/=2;
	}
	a=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			a=((long long)a+ans.a[i][j])%1000000007;
		}	
	}
	printf("%lld",a);
	return 0;
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
ll LCM(int a, int b){
    return a*b/gcd(a,b);
}

int main(void)
{
    string s;
    ll k;
    cin>>s>>k;
    for(ll i=0;i<min((ll)s.size(),k);i++){
        if(s[i]!='1'){
            cout<<s[i]<<endl;
            return 0;
        }
    }
    cout<<1<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

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

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

using namespace std;

int main() {
  int h, w;
  cin >> h >> w;
  char pic[h][w];

  rep(i, h) {
    rep(j, w) {
      cin >> pic[i][j];
    }
  }

  rep(i, h * 2) {
    rep(j, w) {
      cout << pic[i / 2][j];
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2e5 + 5;
const int logk = 60;

int n;
lli m;
int a[maxn];

int f[maxn][logk];

void read_input()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
}

void solve()
{
    for(int i = 1; i <= n; ++i)
        f[i][0] = a[i];
    for(int k = 1; k < logk; ++k)
        for(int i = 1; i <= n; ++i)
            f[i][k] = f[f[i][k - 1]][k - 1];
    int cur = 1;
    for(int k = 0; k < logk; ++k)
        if(m >> k & 1)
            cur = f[cur][k];
    cout << cur << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



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

using namespace std;

int main() {
	int H, W;
	cin>>H>>W;
	vector<vector<char>> g(H, vector<char>(W));
	for (auto &x : g) {
		for (auto &y : x) {
			cin>>y;
		}
	}

	function<int(pair<int, int>)> bfs = [&] (pair<int, int> root) -> int {
		queue<pair<int, int>> q;
		q.push(root);
		vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
		vector<vector<int>> d(H, vector<int>(W));
		vector<vector<bool>> v(H, vector<bool>(W));
		d[root.first][root.second] = 0;
		v[root.first][root.second] = true;
		while (!q.empty()) {
			pair<int, int> next = q.front();
			q.pop();
			for (int i = 0;i < (int)dirs.size();++i) {
				pair<int, int> next_d = make_pair(dirs[i].first + next.first, dirs[i].second + next.second);
				if (next_d.first < H && next_d.first >= 0 && next_d.second < W && next_d.second >= 0 && g[next_d.first][next_d.second] != '#' && !v[next_d.first][next_d.second] ) {
					q.push(next_d);
					d[next_d.first][next_d.second] = d[next.first][next.second] + 1;
					v[next_d.first][next_d.second] = true;
				}
			}
		}

		int ans = INT_MIN;
		for (auto const &x : d) {
			for (auto const &y : x) {
				ans = max(ans, y);
			}
		}

		return ans;
	};

	int ans = INT_MIN;
	for (int i = 0;i < H;++i) {
		for (int j = 0;j < W;++j) {
			if (g[i][j] != '#') {
				ans = max(ans, bfs(make_pair(i, j)));
			}
		}
	}

	cout<<ans<<endl;

	return 0;
}


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

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#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 sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

struct C{
	int n;
	char c;
	C(){}
	C(int n,int c):n(n),c(c){}
}c[9];

int T;

bool cmp(C a,C b){return a.n<b.n;}

int f(vc<C> v){
	int res=0,l=v.sz;
	if(!l)return 1;
	rep(i,l)rep2(j,i+1,l)rep2(k,j+1,l){
		if((v[i].n==v[j].n&&v[j].n==v[k].n||v[i].n==v[j].n-1&&v[j].n==v[k].n-1)
		&&v[i].c==v[j].c&&v[j].c==v[k].c){
			vc<C> w;
			rep(ii,l)if(ii!=i&&ii!=j&&ii!=k)w.pb(v[ii]);
			res|=f(w);
		}
	}
	return res;
}

int main(){
	cin>>T;
	while(T--){
		rep(i,9)cin>>c[i].n;
		rep(i,9)cin>>c[i].c;
		sort(c,c+9,cmp);
		vc<C> v;
		rep(i,9)v.pb(c[i]);
		cout<<f(v)<<endl;
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vi k(n);
    rep(i,n)cin>>k[i];
    bool c=true;
    int t=0;
    rep(i,n)
      if(k[i]>=2)c=false;
      else if(k[i]==0)t++;
    if(c) cout<<"NA"<<endl;
    else  cout<<n+1-t<<endl;
  }
}

Measured memory_bytes: 3128
n = int(input())
vector_x = [int(x) for x in input().split()]
vector_y = [int(y) for y in input().split()]

distance_m = 0
distance_u = 0
distance_p3 = 0
distance_mic = 0

for i in range(n):
    distance_m += abs(vector_x[i] - vector_y[i])
    distance_u += abs(vector_x[i] - vector_y[i]) ** 2
    distance_p3 += abs(vector_x[i] - vector_y[i]) ** 3
    if distance_mic < abs(vector_x[i] - vector_y[i]):
        distance_mic = abs(vector_x[i] - vector_y[i])

print(distance_m)
print(distance_u ** (1/2))
print(distance_p3 ** (1/3))
print(float(distance_mic))


Measured memory_bytes: 5648
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 210;
int g[maxn][maxn], G[maxn][maxn];
bool vis[maxn];
int n, m, R, ans;
int r[10];

void dfs(int cur, int dep, int sum) {
    if(dep == R) {
        ans = min(ans, sum);
        return;
    }
    for(int i = 1; i <= R; ++i) {
        if(vis[i] || G[cur][i] == inf) continue;
        vis[i] = true;
        dfs(i, dep + 1, sum + G[cur][i]);
        vis[i] = false;
    }
}

int main(void) {
    while(~scanf("%d%d%d", &n, &m, &R)) {
        for(int i = 1; i <= R; ++i) scanf("%d", r + i);
        for(int i = 1; i <= n; ++i) {
            g[i][i] = 0;
            for(int j = i + 1; j <= n; ++j)
                g[i][j] = g[j][i] = inf;
        }
        int a, b, c;
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = min(c, g[a][b]);
        }
        for(int k = 1; k <= n; ++k) {
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= n; ++j)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
        memset(G, inf, sizeof(G));
        for(int i = 1; i <= R; ++i) {
            G[i][i] = 0;
            for(int j = i + 1; j <= R; ++j)
                G[i][j] = G[j][i] = g[r[i]][r[j]];
        }
        ans = inf;
        for(int i = 1; i <= n; ++i) {
            memset(vis, false, sizeof(vis));
            vis[i] = true;
            dfs(i, 1, 0);
        }
        printf("%d\n", ans);
    }
}


Measured memory_bytes: 640
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

def resolve():

    N,M=map(int,input().split())
    A=[int(input()) for i in range(M)]


    dp=[1]*(N+1)
    for i in A:
        dp[i]=0

    for i in range(2,N+1):
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)*dp[i]

    print(dp[N])

resolve()

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

int main(){
  string sa,sb,sc;
  cin >> sa >> sb >> sc;
  int turn=0;
  
  while(1){
    if(turn == 0){
      if(sa.size() == 0) break;
      char a = sa.at(0);
      sa.erase(sa.begin() + 0);
      if(a == 'b'){
        turn = 1;
      }else if(a == 'c'){
        turn = 2;
      }
    }else if(turn == 1){
      if(sb.size() == 0) break;
      char a = sb.at(0);
      sb.erase(sb.begin() + 0);
      if(a == 'a'){
        turn = 0;
      }else if(a == 'c'){
        turn = 2;
      }
    }else if(turn == 2){
      if(sc.size() == 0) break;
      char a = sc.at(0);
      sc.erase(sc.begin() + 0);
      if(a == 'a'){
        turn = 0;
      }else if(a == 'b'){
        turn = 1;
      }
    }
  }
  
  if(turn == 0){
    cout << 'A' << endl;
  }else if(turn == 1){
    cout << 'B' << endl;
  }else if(turn == 2){
    cout << 'C' << endl;
  }
}

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

int v[210000], L[210000], R[210000];
//利用L,R数组记录某个点的左右关系

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	for (int i = 0; i < a; ++i)
	{
		v[i] = 1;
        L[i] = (i + a - 1) % a;
        R[i] = (i + 1) % a;
	}
	int now = 0, d;
	for (int i = 0; i < b; ++i){
		scanf("%d", &d);
		if (d % 2){
			//找到当前个人左边的第d个人
			for (int j = 0; j < d; ++j)now = L[now];
			v[now] = 0;
			int l = L[now], r = R[now];
			R[l] = r;
			L[r] = l;
			now = r;
		}else{
			//找到当前个人左边的第d个人
			for (int j = 0; j < d; ++j)now = R[now];
			v[now] = 0;
			int l = L[now], r = R[now];
			R[l] = r;
			L[r] = l;
			now = r;
		}
		
	}
	for (int i = 0; i < c; ++i){
		int d;
		scanf("%d", &d);
		printf("%d\n", v[d]);
	}
	return 0;
}


Measured memory_bytes: 5464
#include <iostream>

using namespace std;

using ll = long long;

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()

typedef pair<int, int> P;

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, k;
	cin >> n >> k;
	int a[n];
	REP(i, n) cin >> a[i];
	
	n -= k;
	int cnt = 1;
	while (n > 0) {
		cnt++;
		n -= (k - 1);
	}
	
	cout << cnt << endl;
	
	return 0;
}

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

DP = [[0, 0, 0] for _ in range(N+1)]

for i in range(1, N+1):
    a, b, c = map(int, input().split())
    DP[i][0] = max(DP[i - 1][1] + a, DP[i - 1][2] + a)
    DP[i][1] = max(DP[i - 1][0] + b, DP[i - 1][2] + b)
    DP[i][2] = max(DP[i - 1][0] + c, DP[i - 1][1] + c)


print(max(DP[N]))


Measured memory_bytes: 28584
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
	int n ;cin >> n;
	for(int k=1;k<=n;k++)
	{
	string str[8]; for(int i=0;i<8;i++) cin >> str[i] ;
	bool bom[8][8];
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
		{
			char ch; ch=str[i][j];
			bom[i][j]=ch-'0';
		}
	}
	int x0,y0; cin >> x0 >> y0 ;
	queue<int> qx,qy;
	qx.push(x0-1); qy.push(y0-1);
	while(!qx.empty())
	{
		int x=qx.front(); qx.pop();
		int y=qy.front(); qy.pop();
		if(!bom[y][x]) continue;
		bom[y][x]=false;
		for(int i=-3;i<=3;i++)
			if(0<=y+i && y+i<=7 && bom[y+i][x]) qx.push(x), qy.push(y+i);
		for(int j=-3;j<=3;j++)
			if(0<=x+j && x+j<=7 && bom[y][x+j]) qx.push(x+j),qy.push(y);
	}
	cout << "Data " << k  << ":" << endl;
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
			cout << noboolalpha << bom[i][j] ;
		cout << endl;
	}
	}
}

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

using namespace std;

#define REP(i,m) for(ll i=0; i<m; i++)
#define FOR(i,n,m) for(ll i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

ll POW(ll a, ll b){
	if(b==1) return a;
	if(b%2==0) return POW(a*a%INF, b/2);
	return a*POW(a, b-1)%INF;
}

int main(){
	int h, w;
	cin >> h >> w;
	string s[h];
	REP(i, h) cin >> s[i];
	int a[h][w], b[h][w], c[h][w], d[h][w];
	REP(i, h){
		int t = 0;
		REP(j, w){
			if(s[i][j] == '#') t = 0;
			else t++;
			a[i][j] = t;
		}
	}
	REP(i, h){
		int t = 0;
		REP(j, w){
			if(s[i][w-1-j] == '#') t = 0;
			else t++;
			b[i][w-1-j] = t;
		}
	}
	REP(j, w){
		int t = 0;
		REP(i, h){
			if(s[i][j] == '#') t = 0;
			else t++;
			c[i][j] = t;
		}
	}
	REP(j, w){
		int t = 0;
		REP(i, h){
			if(s[h-1-i][j] == '#') t = 0;
			else t++;
			d[h-1-i][j] = t;
		}
	}
	int ans = 0;
	REP(i, h){
		REP(j, w){
			ans = max(ans, a[i][j]+b[i][j]+c[i][j]+d[i][j]-3);
		}
	}
	cout << ans << endl;
	return 0;
} 


Measured memory_bytes: 66816
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N,D; cin >> N >> D;
	VV<int> a2bs(100010);
	rep(i,N){
		int a,b; cin >> a >> b;
		a2bs[a].pb(b);
	}
	priority_queue<int> q;
	int ans = 0;
	for(int d=D-1;d>=0;d--){
		for(int b: a2bs[D-d]) q.push(b);
		if(!q.empty()){
			ans += q.top(); q.pop();
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 5632
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Math;

namespace CSharpSpiral {
	class Program {
		static void Main(string[] args) {
			var sw = new StreamWriter(Console.OpenStandardOutput()) {
				AutoFlush =
#if DEBUG
			true
#else
			false
#endif
			};
			Console.SetOut(sw);
			new Program().Solve(new ConsoleInput(
#if DEBUG
			new StreamReader("../../../inputData.txt")
#else
			Console.In
#endif
			, ' '));
			Console.Out.Flush();
		}
		public void Solve(ConsoleInput cin) {
			var N = cin.ReadInt;
			var M = cin.ReadInt;
			var A = cin.ReadIntArray(N);
			var sum = A.Sum();
			var Res = A.Count(x => x * 4 * M >= sum)>=M;
			Console.WriteLine(Res?"Yes":"No");
		}
	}
	static class ExtendClass {
		public static string Join<T>(this IEnumerable<T> X, string separator = " ") => string.Join(separator, X);

	}
	class ConsoleInput {
		private readonly TextReader _stream;
		private readonly char _separator = ' ';
		private readonly Queue<string> inputStream;
		public ConsoleInput(TextReader stream, char separator = ' ') {
			this._separator = separator;
			this._stream = stream;
			inputStream = new Queue<string>();
		}
		public string Read {
			get {
				if(inputStream.Count != 0) return inputStream.Dequeue();
				string[] tmp = _stream.ReadLine().Split(_separator);
				for(int i = 0; i < tmp.Length; ++i)
					inputStream.Enqueue(tmp[i]);
				return inputStream.Dequeue();
			}
		}
		public string ReadLine { get { return _stream.ReadLine(); } }
		public int ReadInt { get { return int.Parse(Read); } }
		public long ReadLong { get { return long.Parse(Read); } }
		public double ReadDouble { get { return double.Parse(Read); } }
		public string[] ReadStrArray(long N) {
			var ret = new string[N];
			for(long i = 0; i < N; ++i)
				ret[i] = Read;
			return ret;
		}
		public int[] ReadIntArray(long N) { var ret = new int[N]; for(long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
		public long[] ReadLongArray(long N) { var ret = new long[N]; for(long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
		public double[] ReadDoubleArray(long N) { var ret = new double[N]; for(long i = 0; i < N; ++i) ret[i] = ReadDouble; return ret; }
		public bool isEOF {
			get { return _stream.Peek() == -1; }
		}
	}

}


Measured memory_bytes: 13396
#include <iostream>

using namespace std;

int n, m, res, Count;
int a[55][55];
int Number[55], Low[55], Parent[55];

void Visit(int u)
{
	++Count;
	Number[u] = Count;
	Low[u] = n + 1;

	for (int v = 1; v <= n; ++v)
		if (a[u][v])
		{
			a[v][u] = 0;

			if (Parent[v] == 0)
			{
				Parent[v] = u;
				Visit(v);
				if (Low[u] > Low[v])
					Low[u] = Low[v];
			}
			else
			{
				if (Low[u] > Number[v])
					Low[u] = Number[v];
			}
		}
}

int main()
{
	int u, v;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		cin >> u >> v;
		a[u][v] = 1;
		a[v][u] = 1;
	}

	for (u = 1; u <= n; ++u)
		if (Parent[u] == 0)
		{
			Parent[u] = -1;
			Visit(u);
		}

	for (v = 1; v <= n; ++v)
	{
		u = Parent[v];

		if (u != -1 && Low[v] >= Number[v])
			++res;
	}

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int b,r,t;
	int r1;
	int i,j,n,x,y,max1,max2,answer1,answer2;
	scanf("%d",&n);
	while(n!=0) {
		scanf("%d",&y);
		max1=0;
		for(i=1;i<=n;i++) {
			scanf("%d %d %d",&b,&r,&t);
			if(t==1) {
				r1=10000*r/100*y;
				answer1=r1+10000;
			}
			answer2=10000;
			if(t==2) {
				for(j=1;j<=y;j++) {
					answer2=answer2*r/100+answer2;
				}
				answer1=answer2;
			}
			if (answer1 > max1) {
				max1=answer1;
				max2=b;
			}
		}
		printf ("%d\n",max2);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

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

const int MAX_N = 1 << 19;

int n;
bool dat[26][2*MAX_N-1];

void init(int n_) {
    n = 1;
    while (n < n_) n *= 2;

    Rep (i, 2*n-1) Rep (j, 26) dat[j][i] = false;
}

void update(int k, bool a, char c) {
    k += n-1;
    ll num = c - 'a';
    dat[num][k] = a;
    while (k > 0) {
        k = (k-1) / 2;
        dat[num][k] = dat[num][k*2+1] || dat[num][k*2+2];
    }
}

bool query(ll a, ll b, ll k, ll l, ll r, char c) {
    if (r <= a || b <= l) return false;

    ll num = c - 'a';
    if (a <= l && r <= b) return dat[num][k];
    else {
        bool vl = query(a, b, k*2+1, l, (l+r) / 2, c);
        bool vr = query(a, b, k*2+2, (l+r) / 2, r, c);
        return vl || vr;
    }
}

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

    ll N, Q;
    string S;
    cin >> N >> S >> Q;

    init(N);

    Rep (i, 26) {
        Rep (j, N) {
            if (S[j] == 'a' + i) {
                update(j, true, S[j]);
            }
        }
    }

    while (Q--) {
        ll q;
        cin >> q;
        if (q == 1) {
            ll i; char c;
            cin >> i >> c;
            i--;
            update(i, false, S[i]);
            update(i, true, c);
            S[i] = c;
        } else {
            ll l, r;
            cin >> l >> r;
            l--;
            ll cnt = 0;
            Rep (i, 26) {
                cnt += query(l, r, 0, 0, n, 'a' + i);
            }
            cout << cnt << "\n";
        }
    }

}

Measured memory_bytes: 27548
import sys
input=sys.stdin.readline
from random import seed, randint

def calc(d,C,S,T):
    Last=[0]*26
    score=0
    for day,t in enumerate(T):
        t-=1
        Last[t]=day+1
        score+=S[day][t]
        for i,c in enumerate(C):
            score-=c*(day+1-Last[i])
    return score

def main():
    d=int(input())
    C=tuple(map(int,input().split()))
    S=[tuple(map(int,input().split())) for _ in range(d)]
    Ans=[0]*d
    Last=[0]*26
    
    #貪欲法
    for day in range(d):
        ans=0
        score=-float('inf')
        for t in range(26):
            TmpList=Last[:]
            tmp_score=0
            TmpList[t]=day+1
            for i,c in enumerate(C):
                tmp_score-=c*(day+1-TmpList[i])
            if tmp_score>score:
                score=tmp_score
                ans=t+1
        Ans[day]=ans
        Last[ans-1]=day
    
    score=calc(d,C,S,Ans)
    #print(score)
    
    #局所探索法
    T=Ans[:]
    m=5000
    for i in range(m):
        seed(i)
        d_idx=randint(0,d-1)
        q=randint(1,26)
        #print(d_idx,q)
        T[d_idx]=q
        tmp=calc(d,C,S,T)
        if tmp>score:
            score=tmp
            Ans=T[:]
    #print(score)
    
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()

Measured memory_bytes: 80824
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <numeric> // accumulate(begin,end,初期値)


// ------------debug用------------
#define FALSE cout<<"false"<<endl;
#define TRUE cout<<"true"<<endl;
// ------------debug用------------


// ------------計算用------------
#define ALL(x) (x).begin(),(x).end()
#define FOR(x) for(ll i = 0;i < x;++i)
// ------------計算用------------


// ------------出力用------------
#define PRINT(x) cout<<x<<endl;
// ------------出力用------------


using namespace std;
typedef long long ll;

int main(){
  double W,H,x,y;
  cin>>W>>H>>x>>y;
  double ans = 0;
  bool isHalfW = W / 2 == x;
  bool isHalfH = H / 2 == y;
  
  if(isHalfW && isHalfH){
    ans = W * H / 2;
    cout<<ans<<" "<<'1';
    return 0;
  }else{
    ans = W * H / 2;
    cout<<ans<<" 0";
    return 0;
  }
  
  
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
static const int MAX = 100000;

int main() {
  int n, v[MAX+1], t, res = 0;
  v[0] = -1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> v[i+1];
    v[i] >= v[i+1] ? t++ : t = 0;
    if (res < t) res = t;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramC
    {
        static void Main()
        {
            int n = NextInt;
            var array = IntList;
            var result = Enumerable.Repeat(0, n).ToArray();

            for (int i = 0; i < n - 1; i++)
            {
                result[array[i] - 1]++;
            }

            System.Console.WriteLine(string.Join("\n", result));
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 45460