Submission #868714

#	Time	Username	Problem	Language	Result	Execution time	Memory
868714		MON	Feast (NOI19_feast)	C++14	4 / 100	196 ms	15912 KiB

feast

#include<iostream>
#include<vector>
#warning we made it
using namespace std;
using ll = long long;
using pii = pair<int,long long>;

constexpr int NMAX = 3e5 + 1;
const ll oo = (1LL << 62);

int a[NMAX];

inline pii best(pii a,pii b)
{
   if(a.second != b.second) return (a.second > b.second ? a : b);
   return (a.first < b.first ? a : b);
}

pii solve(int n,int l)
{
    vector<pii> dp[2]; dp[0].resize(n + 1,{0,-oo}),dp[1].resize(n + 1,{0,-oo}); //dp[i] = suma maxima pana in i daca costul pentru a deschide o subsecventa este l

    dp[0][0] = {0,0};
    for(int i = 0 ; i < n ; i++)
        {
            dp[0][i + 1] = best(dp[0][i],dp[1][i]);
            dp[1][i + 1] = best({dp[1][i].first,dp[1][i].second + a[i + 1]},{dp[0][i].first + 1,dp[0][i].second + a[i + 1] - l});
        }

    return best(dp[0][n],dp[1][n]);
}

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

    int st = 0 , dr = 1 << 29 , lambda;
    while(st <= dr)
        {
            int mid = st + (dr - st) / 2; pii now = solve(n,mid);
            if(now.first <= k) dr = mid - 1,lambda = mid;
            else st = mid + 1;
        }

    pii ans = solve(n,lambda);
    ll out = ans.second + 1LL * lambda * ans.first;

    cout << out;
}

Compilation message (stderr)

feast.cpp:3:2: warning: #warning we made it [-Wcpp]
    3 | #warning we made it
      |  ^~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:47:33: warning: 'lambda' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     ll out = ans.second + 1LL * lambda * ans.first;
      |                                 ^~~~~~

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