Submission #747030

#	Time	Username	Problem	Language	Result	Execution time	Memory
747030		nguyentunglam	Cake 3 (JOI19_cake3)	C++17	24 / 100	808 ms	4144 KiB

cake3

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

long long calc(int i, int j) {
    if (j - i + 1 < m) return -1e18;
    vector<int> lst;
    for(int k = i + 1; k <= j - 1; k++) lst.push_back(a[k].first);
    sort(lst.begin(), lst.end(), greater<int>());
    long long tmp = a[i].first + a[j].first;
    for(int k = 0; k < m - 2; k++) tmp += lst[k];
    return tmp - (a[j].second - a[i].second) * 2;
}
void solve(int l, int r, int from, int to) {
    if (l > r) return;
    int mid = l + r >> 1;
    long long f = -2e18, g = 0;
    for(int j = from; j <= to && j <= mid; j++) {
        long long tmp = calc(j, mid);
        if (tmp > f) {
            f = tmp;
            g = j;
        }
    }
//    cout << l << " " << r << " " << mid << " " << f << " " << g << endl;
    ans = max(ans, f);
    solve(l, mid - 1, from, g);
    solve(mid + 1, r, g, to);
}
int 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);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1, [] (const ii &x, const ii &y) {
         return x.se < y.se;
         });
    solve(1, n, 1, n);
    cout << ans;
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:41:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:42:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:45:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:46:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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