Submission #1247702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247702		TheSahib	Feast (NOI19_feast)	C++20	100 / 100	115 ms	12168 KiB

feast

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int inf = 1e18 + 9;
const int MAX = 2e5 + 5;
const int LOG = 20;
const int MOD = 998244353;

void solve(){
    int n, k; cin >> n >> k;
    int arr[n + 1];
    for(int i = 1; i <= n; ++i){
        cin >> arr[i];
    }

    auto get = [&](int pen){
        array<int, 2> dp[n + 1][2];
        dp[1][0] = {0, 0};
        dp[1][1] = {arr[1] - pen, 1};
        for(int i = 2; i <= n; ++i){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = max((array<int, 2>){dp[i - 1][1][0] + arr[i], dp[i - 1][1][1]}, 
                           (array<int, 2>){dp[i - 1][0][0] - pen + arr[i], dp[i - 1][0][1] + 1});
        }
        array<int, 2> mx = max(dp[n][0], dp[n][1]);
        return mx;
    };

    int l = 0, r = 3e14 + 100;
    while(l < r){
        int mid = (l + r + 1) / 2;
        auto mx = get(mid);
        if(mx[1] >= k){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    auto a = get(l);
    cout << a[0] + k * l << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1; 
    // cin >> t;
    while(t){
        t--;
        solve();
    }
}

• 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