Submission #4060890

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <utility>
#include <queue>
#include <set>

#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; i++)
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 (a > b) {a = b; return 1;} return 0; }

typedef long long ll;
using namespace std;

int main() {
    
    ll k, n;
    cin >> n >> k;
    vector<vector<ll>> td(n, vector<ll>(3, 0));
    REP(i, n) {
        cin >> td[i][0] >> td[i][1];
        td[i][2] = 0;
    }

    sort(ALL_OF(td), [](vector<ll> &a, vector<ll>& b) -> bool {
        return a[1] > b[1];
    });

    vector<bool> m(n+1, false);
    ll bonus = 1;
    ll ans = 0;
    REP(i, n) {
        if (!m[td[i][0]]) {
            m[td[i][0]] = true;
            td[i][2] = bonus;
            bonus += 2;
        }
        if (i < k) ans += td[i][1] + td[i][2];
    }
    
    int l = k, r = k-1;
    ll cand = ans;
    while (true) {
        for (l--; l >= 0; l--) if (td[l][2] == 0) break;
        for (r++; r < n; r++) if (td[r][2] != 0) break;
        if (l < 0 || r >= n) break;
        cand += td[r][1] + td[r][2] - td[l][1];
        chmax(ans, cand);
    }
    
    cout << ans << endl;

}

Submission Info

Judge Result