oj.uz

Submission #868719

# Submission time Handle Problem Language Result Execution time Memory
868719 2023-11-01T18:28:57 Z MON Feast (NOI19_feast) C++14
4 / 100
 1000 ms 10836 KB 
#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 = 1e16;

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)
{
    pii dp[2][n + 1]; dp[0][0] = {0,0},dp[1][0] = {0,-oo};
    for(int i = 0 ; i < n ; i++)
        {
            dp[0][i + 1] = best(dp[0][i],dp[1][i]);
            dp[1][i + 1] = best({dp[0][i].first + 1,dp[0][i].second + a[i + 1] - l},
                                {dp[1][i].first,dp[1][i].second + a[i + 1]});
        }
    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];

    ll st = 0 , dr = 1LL << 62 , lambda(0);
    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;
    //solve(n,1);

}

Compilation message

feast.cpp:3:2: warning: #warning we made it [-Wcpp]
    3 | #warning we made it
      |  ^~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10580 KB Output is correct
2 Correct 85 ms 10828 KB Output is correct
3 Correct 86 ms 10836 KB Output is correct
4 Correct 88 ms 10832 KB Output is correct
5 Correct 85 ms 10832 KB Output is correct
6 Correct 83 ms 10576 KB Output is correct
7 Correct 83 ms 10576 KB Output is correct
8 Correct 86 ms 10832 KB Output is correct
9 Correct 84 ms 10580 KB Output is correct
10 Correct 84 ms 10576 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 10588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 10716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10580 KB Output is correct
2 Correct 85 ms 10828 KB Output is correct
3 Correct 86 ms 10836 KB Output is correct
4 Correct 88 ms 10832 KB Output is correct
5 Correct 85 ms 10832 KB Output is correct
6 Correct 83 ms 10576 KB Output is correct
7 Correct 83 ms 10576 KB Output is correct
8 Correct 86 ms 10832 KB Output is correct
9 Correct 84 ms 10580 KB Output is correct
10 Correct 84 ms 10576 KB Output is correct
11 Execution timed out 1016 ms 10588 KB Time limit exceeded
12 Halted 0 ms 0 KB -