Submission #747001

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

cake3

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define int long long
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
int v[N], c[N];

pair<long long, long long> calc(pair<long long, long long> A, pair<long long, long long> B) {
    if (A.first == B.first) return A.second < B.second ? A : B;
    return A.first > B.first ? A : B;
}
main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, m; cin >> n >> m;
    vector<ii> lst;
    for(int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        lst.emplace_back(x, y);
    }
    sort(lst.begin(), lst.end(), [] (const ii &x, const ii &y) {
         return x.se < y.se;
         });
    for(int i = 1; i <= n; i++) tie(v[i], c[i]) = lst[i - 1];
    long long l = -1e12, r = 1e12, ans = 0;
    while (l <= r) {
        long long tax = l + r >> 1;
        pair<long long, long long> f, ret;
        f = ret = make_pair(-1e18, -1e18);
        for(int i = 1; i <= n; i++) {
            ret = max(ret, make_pair(f.first + v[i] - 2 * c[i] - tax, f.second + 1));
            pair<long long, long long> g = make_pair(f.first + v[i] - tax, f.second + 1);
            f = max(f, g);
            f = max(f, make_pair(v[i] + 2 * c[i] - tax, 1LL));
        }
//        cout << ret.first << " " << ret.second << " " << tax << endl;
        if (ret.second >= m) {
            ans = ret.first + m * tax;
            l = tax + 1;
        }
        else r = tax - 1;
    }
    cout << ans;
}

Compilation message (stderr)

cake3.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:39:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         long long tax = l + r >> 1;
      |                         ~~^~~
cake3.cpp:20:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:21:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:24:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:25:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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