Submission #545542

#	Time	Username	Problem	Language	Result	Execution time	Memory
545542		LucaDantas	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	340 KiB

cake3

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

constexpr int maxn = 2e5+10;

long long ans = -0x3f3f3f3f, 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 0;
        return sum;
    }
};

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<pair<int,int>> cakes(n);
    for(pair<int,int>& p : cakes)
        scanf("%d %d", &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(int)':
cake3.cpp:16:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |         if(st.size() > sz)
      |            ~~~~~~~~~~^~~~
cake3.cpp: In member function 'long long int Set::get()':
cake3.cpp:20:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |         if(st.size() < sz) return 0;
      |            ~~~~~~~~~~^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:26:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d %d", &p.first, &p.second), p.second <<= 1;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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