Submission #128782

#	Time	Username	Problem	Language	Result	Execution time	Memory
128782		win11905	Cake 3 (JOI19_cake3)	C++11	0 / 100	11 ms	380 KiB

cake3

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 1e5+5;

int n, m;
long v[N], c[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld %lld", v+i, c+i);
    }
    long ans = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = i+1; j <= n; ++j) {
            priority_queue<long, vector<long>, greater<long> > Q;
            long sum = 0;
            for(int k = 1; k <= n; ++k) if((c[k] >= c[i] && c[k] <= c[j]) || (c[k] >= c[j] && c[k] <= c[i])) {
                if(i != k && j != k) Q.emplace(v[k]), sum += v[k];
            }
            while((int)Q.size() > m-2) sum -= Q.top(), Q.pop();
            ans = max(ans, v[i] + v[j] + sum - 2ll * (abs(c[i] - c[j])));
        }
    }
    printf("%lld\n", ans);
    return 0;
    map<int, vector<int> > Mp;
    vector<pair<int, vector<int> > > vec; 
    for(auto &x : Mp) {
        vec.emplace_back(x);
        sort(all(vec.back().y), greater<int>());
    }
    for(int i = 0; i < vec.size(); ++i) {
        priority_queue<int, vector<int>, greater<int> > Q;
        long sum = 0;
        sum += vec[i].y[0];
        for(int j = 1; j < vec[i].y.size(); ++j) sum += vec[i].y[j], Q.emplace(vec[i].y[j]);
        while(Q.size() > m-1) sum -= Q.top(), Q.pop();
        if(Q.size() == m-1) ans = max(ans, sum);
        for(int j = i+1; j < vec.size(); ++j) {
            for(int k = vec[j].y.size()-1; k > 0; --k) sum += vec[j].y[k], Q.emplace(vec[j].y[k]);
            while(Q.size() > m-2) sum -= Q.top(), Q.pop();
            if(Q.size() == m-2) ans = max(ans, sum + vec[j].y[0] - 2ll * (vec[j].x - vec[i].x));
            sum += vec[j].y[0], Q.emplace(vec[j].y[0]);
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); ++i) {
                    ~~^~~~~~~~~~~~
cake3.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < vec[i].y.size(); ++j) sum += vec[i].y[j], Q.emplace(vec[i].y[j]);
                        ~~^~~~~~~~~~~~~~~~~
cake3.cpp:44:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(Q.size() > m-1) sum -= Q.top(), Q.pop();
               ~~~~~~~~~^~~~~
cake3.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(Q.size() == m-1) ans = max(ans, sum);
            ~~~~~~~~~^~~~~~
cake3.cpp:46:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = i+1; j < vec.size(); ++j) {
                          ~~^~~~~~~~~~~~
cake3.cpp:48:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(Q.size() > m-2) sum -= Q.top(), Q.pop();
                   ~~~~~~~~~^~~~~
cake3.cpp:49:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(Q.size() == m-2) ans = max(ans, sum + vec[j].y[0] - 2ll * (vec[j].x - vec[i].x));
                ~~~~~~~~~^~~~~~
cake3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", v+i, c+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76