Submission #545548

#	Time	Username	Problem	Language	Result	Execution time	Memory
545548		LucaDantas	Cake 3 (JOI19_cake3)	C++17	24 / 100	4038 ms	12720 KiB

cake3

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

#define int long long

constexpr int maxn = 2e5+10;

long long ans = -0x3f3f3f3f3f, val[maxn], c[maxn];

struct Set {
    int sz;
    long long sum = 0;
    multiset<int> st;
    Set(int _sz) : sz(_sz) {}
    void add(int x) {
        sum += x;
        st.insert(x);
        if(st.size() > sz)
            sum -= *st.begin(), st.erase(st.begin());
    }
    long long get() {
        if(st.size() < sz) return -0x3f3f3f3f3f;
        return sum;
    }
};

int32_t main() {
    int n, m; scanf("%lld %lld", &n, &m);
    vector<pair<int,int>> cakes(n);
    for(pair<int,int>& p : cakes)
        scanf("%lld %lld", &p.first, &p.second), p.second <<= 1;
    sort(cakes.begin(), cakes.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
    for(int i = 0; i < n; i++)
        tie(val[i], c[i]) = cakes[i];

    for(int l = 0; l < n; l++) {
        Set st(m);
        for(int r = l; r < n; r++)
            st.add(val[r]), ans = max(ans, st.get() - c[r] + c[l]);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

cake3.cpp: In member function 'void Set::add(long long int)':
cake3.cpp:18:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |         if(st.size() > sz)
      |            ~~~~~~~~~~^~~~
cake3.cpp: In member function 'long long int Set::get()':
cake3.cpp:22:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   22 |         if(st.size() < sz) return -0x3f3f3f3f3f;
      |            ~~~~~~~~~~^~~~
cake3.cpp: In function 'int32_t main()':
cake3.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     int n, m; scanf("%lld %lld", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~
cake3.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld %lld", &p.first, &p.second), p.second <<= 1;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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