Submission #4075597

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

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

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

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

typedef ull V;
typedef pair<V, V> pVV;
const V INF_V = LLONG_MAX;
const int ME = 17;
const int N = 1<<ME;
class RMQ_segtree{
public:
    pVV dat[2*N-1];
    RMQ_segtree(){
        REP(i, 2*N-1) dat[i] = make_pair(INF_V, -1);
    }

    void update(int k, V a){
        //k番目の要素をaに変更
        k += N-1;
        dat[k] = make_pair(a, k-(N-1));
        while(k>0){
            k = (k-1)/2;
            dat[k] = min(dat[2*k+1], dat[2*k+2]);
        }
    }

   pVV recursion(int a, int b, int k, int l, int r){
        //最小値計算用の再帰関数
        if(r<=a || b<=l) return make_pair(INF_V, -1);
        if(a<=l && r<=b) return dat[k];
        else{
            pVV vl = recursion(a, b, 2*k+1, l, (l+r)/2);
            pVV vr = recursion(a, b, 2*k+2, (l+r)/2, r);
            return min(vl, vr);
        }
    }

    pVV minimum(int a, int b){
        //区間[a, b)の最小値
        return recursion(a, b, 0, 0, N);
    }

    void print_val(int a, int b){
        //区間[a, b)の値を出力
        for(int i=a;i<b;i++) cout << dat[i+N-1].first << endl;
        cout << endl;
    }
};

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

	RMQ_segtree se;
	REP(i, N) se.update(i, a[i]);
	ull res = 0;
	REP(i, K){
		pVV tmp =  se.minimum(0, N);
		res += tmp.first;
		se.update(tmp.second, tmp.first+b[tmp.second]);
	}
	cout << res << endl;
    return 0;
}

Submission Info

Judge Result