oj.uz

Submission #595994

# Submission time Handle Problem Language Result Execution time Memory
595994 2022-07-14T08:48:19 Z Tenis0206 Feast (NOI19_feast) C++11
12 / 100
 102 ms 14396 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = 0x3f3f3f3f;

int n,k;
int v[300005];
int sp[300005];

pair<int,int> dp[300005][2];

pair<int,int> get_val(int c)
{
    /* int Max = 0, nrval = 0;
     int Max_pref = 0, nrval_pref = 0;
     for(int i=1;i<=n;i++)
     {
         dp[i].first = Max_pref + sp[i] - c;
         dp[i].second = nrval_pref + 1;
         if(dp[i].first > Max || (dp[i].first==Max && dp[i].second < nrval))
         {
             Max = dp[i].first;
             nrval = dp[i].second;
         }
         if(Max - sp[i] > Max_pref || (Max - sp[i]==Max_pref && nrval < nrval_pref))
         {
             Max_pref = Max - sp[i];
             nrval_pref = nrval;
         }
     }
     */
    dp[0][1].first = -oo;
    for(int i=1; i<=n+1; i++)
    {
        if(dp[i-1][0]>=dp[i-1][1])
        {
            dp[i][0] = dp[i-1][0];
        }
        else
        {
            dp[i][0] = dp[i-1][1];
        }
        if(pair<int,int>{dp[i-1][1].first + v[i], dp[i-1][1].second} >= pair<int,int>{dp[i-1][0].first + v[i] - c, dp[i-1][0].second + 1})
        {
            dp[i][1] = {dp[i-1][1].first + v[i], dp[i-1][1].second};
        }
        else
        {
            dp[i][1] = {dp[i-1][0].first + v[i] - c, dp[i-1][0].second + 1};
        }
    }
    return dp[n+1][0];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    int st = 0;
    int dr = 1e15;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1LL;
        pair<int,int> val = get_val(mij);
        if(val.second==k)
        {
            cout<<val.first + k * mij<<'\n';
            return 0;
        }
        if(val.second<k)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    pair<int,int> val = get_val(st);
    cout<<val.first + k * st<<'\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 13908 KB Output is correct
2 Correct 90 ms 14220 KB Output is correct
3 Correct 90 ms 14292 KB Output is correct
4 Correct 102 ms 14284 KB Output is correct
5 Correct 90 ms 14204 KB Output is correct
6 Correct 87 ms 13972 KB Output is correct
7 Correct 86 ms 13960 KB Output is correct
8 Correct 96 ms 14156 KB Output is correct
9 Correct 94 ms 13964 KB Output is correct
10 Correct 102 ms 14144 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 14064 KB Output is correct
2 Correct 48 ms 14360 KB Output is correct
3 Correct 46 ms 13996 KB Output is correct
4 Correct 80 ms 14164 KB Output is correct
5 Correct 56 ms 13980 KB Output is correct
6 Correct 49 ms 14036 KB Output is correct
7 Correct 80 ms 14396 KB Output is correct
8 Correct 57 ms 14252 KB Output is correct
9 Correct 53 ms 13888 KB Output is correct
10 Correct 86 ms 14288 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 13908 KB Output is correct
2 Correct 90 ms 14220 KB Output is correct
3 Correct 90 ms 14292 KB Output is correct
4 Correct 102 ms 14284 KB Output is correct
5 Correct 90 ms 14204 KB Output is correct
6 Correct 87 ms 13972 KB Output is correct
7 Correct 86 ms 13960 KB Output is correct
8 Correct 96 ms 14156 KB Output is correct
9 Correct 94 ms 13964 KB Output is correct
10 Correct 102 ms 14144 KB Output is correct
11 Correct 58 ms 14064 KB Output is correct
12 Correct 48 ms 14360 KB Output is correct
13 Correct 46 ms 13996 KB Output is correct
14 Correct 80 ms 14164 KB Output is correct
15 Correct 56 ms 13980 KB Output is correct
16 Correct 49 ms 14036 KB Output is correct
17 Correct 80 ms 14396 KB Output is correct
18 Correct 57 ms 14252 KB Output is correct
19 Correct 53 ms 13888 KB Output is correct
20 Correct 86 ms 14288 KB Output is correct
21 Incorrect 58 ms 14240 KB Output isn't correct
22 Halted 0 ms 0 KB -