oj.uz

Submission #868716

# Submission time Handle Problem Language Result Execution time Memory
868716 2023-11-01T18:09:55 Z MON Feast (NOI19_feast) C++14
4 / 100
 150 ms 10868 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];

    int st = 0 , dr = 1 << 28 , 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 139 ms 10432 KB Output is correct
2 Correct 141 ms 10692 KB Output is correct
3 Correct 141 ms 10832 KB Output is correct
4 Correct 139 ms 10832 KB Output is correct
5 Correct 142 ms 10832 KB Output is correct
6 Correct 141 ms 10656 KB Output is correct
7 Correct 139 ms 10576 KB Output is correct
8 Correct 141 ms 10836 KB Output is correct
9 Correct 143 ms 10652 KB Output is correct
10 Correct 138 ms 10792 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 10580 KB Output is correct
2 Correct 106 ms 10836 KB Output is correct
3 Correct 104 ms 10800 KB Output is correct
4 Correct 103 ms 10580 KB Output is correct
5 Incorrect 140 ms 10576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 10868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 10432 KB Output is correct
2 Correct 141 ms 10692 KB Output is correct
3 Correct 141 ms 10832 KB Output is correct
4 Correct 139 ms 10832 KB Output is correct
5 Correct 142 ms 10832 KB Output is correct
6 Correct 141 ms 10656 KB Output is correct
7 Correct 139 ms 10576 KB Output is correct
8 Correct 141 ms 10836 KB Output is correct
9 Correct 143 ms 10652 KB Output is correct
10 Correct 138 ms 10792 KB Output is correct
11 Correct 102 ms 10580 KB Output is correct
12 Correct 106 ms 10836 KB Output is correct
13 Correct 104 ms 10800 KB Output is correct
14 Correct 103 ms 10580 KB Output is correct
15 Incorrect 140 ms 10576 KB Output isn't correct
16 Halted 0 ms 0 KB -