Submission #1017392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017392		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	119 ms	14980 KiB

feast

// NOI19 Task 3: Feast
// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

ll n,k,a[maxn],L,R,mid;
pair<ll,ll> dp[2][maxn];

pair<ll,ll> check(ll lambda){
    // Penalty is lambda per subarray
    dp[0][1] = {0,0};
    dp[1][1] = {a[1] - lambda,1};
    for(ll i=2;i<=n;i++){
        dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
        dp[1][i] = max(make_pair(dp[1][i-1].first + a[i], dp[1][i-1].second),
                       make_pair(dp[0][i-1].first + a[i] - lambda, dp[0][i-1].second + 1));
    }
    return max(dp[0][n], dp[1][n]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,n) cin >> a[i];
    L = 0; R = 1e18;
    while(L < R){
        mid = (L+R+1)/2;
        if(check(mid).second >= k) L = mid;
        else R = mid-1;
    }
    // cout << L << ' ' << R << ' ' << check(L).second;el;
    pair<ll,ll> res = check(L);
    // cout << res.second;el;
    cout << res.first + k * L;
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(__file_name ".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