Submission #1175011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175011		nhamtan	Feast (NOI19_feast)	C++20	100 / 100	104 ms	21580 KiB

feast

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

#define int long long

const int N = 1e6 + 5;
int n , k;
int a[N];
pair < int , int > dp[N][4];

pair < int , int > check(int mid)
{
    dp[1][0] = {0 , 0};
    dp[1][1] = {a[1] - mid , 1};
    for(int i = 2 ; 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] - mid , dp[i - 1][0].second + 1),
                        make_pair(dp[i - 1][1].first + a[i] , dp[i - 1][1].second));
    }
    return max(dp[n][0] , dp[n][1]);
}

main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
    int l = 1 , r = 3e14 , ans = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid).second >= k)
            l = mid + 1 , ans = mid;
        else
            r = mid - 1;
    }
    cout << check(ans).first + k * ans;
}

Compilation message (stderr)

feast.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main()
      | ^~~~

• 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