oj.uz

Submission #868714

# Submission time Handle Problem Language Result Execution time Memory
868714 2023-11-01T17:46:06 Z MON Feast (NOI19_feast) C++14
4 / 100
 196 ms 15912 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 = (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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 13396 KB Output is correct
2 Correct 177 ms 13752 KB Output is correct
3 Correct 196 ms 13940 KB Output is correct
4 Correct 171 ms 13824 KB Output is correct
5 Correct 182 ms 13756 KB Output is correct
6 Correct 181 ms 13612 KB Output is correct
7 Correct 159 ms 13424 KB Output is correct
8 Correct 153 ms 13744 KB Output is correct
9 Correct 174 ms 13752 KB Output is correct
10 Correct 175 ms 13700 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 11948 KB Output is correct
2 Correct 142 ms 12172 KB Output is correct
3 Correct 136 ms 11860 KB Output is correct
4 Correct 140 ms 11976 KB Output is correct
5 Incorrect 175 ms 13508 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 15912 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 172 ms 13396 KB Output is correct
2 Correct 177 ms 13752 KB Output is correct
3 Correct 196 ms 13940 KB Output is correct
4 Correct 171 ms 13824 KB Output is correct
5 Correct 182 ms 13756 KB Output is correct
6 Correct 181 ms 13612 KB Output is correct
7 Correct 159 ms 13424 KB Output is correct
8 Correct 153 ms 13744 KB Output is correct
9 Correct 174 ms 13752 KB Output is correct
10 Correct 175 ms 13700 KB Output is correct
11 Correct 127 ms 11948 KB Output is correct
12 Correct 142 ms 12172 KB Output is correct
13 Correct 136 ms 11860 KB Output is correct
14 Correct 140 ms 11976 KB Output is correct
15 Incorrect 175 ms 13508 KB Output isn't correct
16 Halted 0 ms 0 KB -