oj.uz

Submission #595993

# Submission time Handle Problem Language Result Execution time Memory
595993 2022-07-14T08:47:15 Z Tenis0206 Feast (NOI19_feast) C++11
12 / 100
 109 ms 14352 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 = INT_MAX;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        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 78 ms 13908 KB Output is correct
2 Correct 73 ms 14220 KB Output is correct
3 Correct 98 ms 14256 KB Output is correct
4 Correct 74 ms 14284 KB Output is correct
5 Correct 67 ms 14204 KB Output is correct
6 Correct 74 ms 13920 KB Output is correct
7 Correct 71 ms 13964 KB Output is correct
8 Correct 70 ms 14240 KB Output is correct
9 Correct 67 ms 14004 KB Output is correct
10 Correct 68 ms 14120 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14028 KB Output is correct
2 Correct 31 ms 14352 KB Output is correct
3 Correct 26 ms 14048 KB Output is correct
4 Correct 63 ms 14112 KB Output is correct
5 Correct 42 ms 13908 KB Output is correct
6 Correct 42 ms 13900 KB Output is correct
7 Correct 63 ms 14324 KB Output is correct
8 Correct 45 ms 14308 KB Output is correct
9 Correct 36 ms 13868 KB Output is correct
10 Correct 79 ms 14264 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 14168 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 340 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 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 13908 KB Output is correct
2 Correct 73 ms 14220 KB Output is correct
3 Correct 98 ms 14256 KB Output is correct
4 Correct 74 ms 14284 KB Output is correct
5 Correct 67 ms 14204 KB Output is correct
6 Correct 74 ms 13920 KB Output is correct
7 Correct 71 ms 13964 KB Output is correct
8 Correct 70 ms 14240 KB Output is correct
9 Correct 67 ms 14004 KB Output is correct
10 Correct 68 ms 14120 KB Output is correct
11 Correct 42 ms 14028 KB Output is correct
12 Correct 31 ms 14352 KB Output is correct
13 Correct 26 ms 14048 KB Output is correct
14 Correct 63 ms 14112 KB Output is correct
15 Correct 42 ms 13908 KB Output is correct
16 Correct 42 ms 13900 KB Output is correct
17 Correct 63 ms 14324 KB Output is correct
18 Correct 45 ms 14308 KB Output is correct
19 Correct 36 ms 13868 KB Output is correct
20 Correct 79 ms 14264 KB Output is correct
21 Incorrect 109 ms 14168 KB Output isn't correct
22 Halted 0 ms 0 KB -