Submission #888155

#	Time	Username	Problem	Language	Result	Execution time	Memory
888155		Asamai	Feast (NOI19_feast)	C++17	100 / 100	502 ms	5808 KiB

feast

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     long double           db;

const int MAX_N = 3e5 + 5;
const db inf = 3e14;
const db eps = 1e-3;

int n, k;
int a[MAX_N];
pair<db, int> dp[2][2];
bool curr, nxt;

int check(db lamda) {
    curr = 0, nxt = 1;
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            dp[i][j] = {-inf, -inf};
        }
    }
    dp[curr][0] = {0, 0};
    for (int i = 0; i < n; i++, swap(curr, nxt)) {
        // 0
        maximize(dp[nxt][0], dp[curr][0]);
        maximize(dp[nxt][1], pair<db, int>(dp[curr][0].fi - lamda + (db) a[i + 1], dp[curr][0].se + 1));

        // 1
        maximize(dp[nxt][1], pair<db, int>(dp[curr][1].fi + (db) a[i + 1], dp[curr][1].se));
        maximize(dp[nxt][0], dp[curr][1]);

        for (int j = 0; j <= 1; j++) {
            dp[curr][j] = {-inf, -inf};
        }
    }
    return max(dp[curr][1], dp[curr][0]).se;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen("FEAS.inp", "r")) {
        freopen("FEAS.inp", "r", stdin);
        freopen("FEAS.out", "w", stdout);
    }

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    db low = 0, high = inf;
    while (low + eps < high) {
        db mid = (low + high) / 2;
        if (check(mid) >= k) {
            low = mid;
        }
        else {
            high = mid;
        }
    }

    db ans = low;
    check(ans);
    cout << (ll) round(max(dp[curr][0], dp[curr][1]).fi + ans * k);

    return 0;
}

/*


Saturday, 16 December 2023
14:53:03
*/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("FEAS.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("FEAS.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29