Submission #1281698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281698		Phan_Tien_Dung	Feast (NOI19_feast)	C++20	100 / 100	94 ms	12152 KiB

feast

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

#define int long long

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


const int INF = 1e17;
const int N = 3e5 + 5;

int n, k;
int a[N];
pii dp[N][2];

pii f(int penatly) {
    dp[0][0] = {0, 0};
    dp[0][1] = {-INF, -INF};
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - penatly, dp[i - 1][0].second + 1),
                       make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
//        cout << dp[i][0].first << '-' << dp[i][1].first << ' ';
    }
//    cout << '\n';
    return max(dp[n][0], dp[n][1]);
}


signed main() {
    cin.tie(0)->sync_with_stdio(0);

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

    int penatly = 0, lo = 0, hi = INF;
    while (lo <= hi) {
        int mid = lo + (hi - lo >> 1);
        pii tmp = f(mid);
//        cout << mid << ' ' << tmp.first << ' ' << tmp.second << '\n';
        if (tmp.second < k) {
            hi = mid - 1;
        } else {
            penatly = mid;
            lo = mid + 1;
        }
    }

//    cout << penatly << '\n';
    cout << f(penatly).first + f(penatly).second * penatly;
}

• 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