oj.uz

Submission #595996

# Submission time Handle Problem Language Result Execution time Memory
595996 2022-07-14T08:50:37 Z Tenis0206 Feast (NOI19_feast) C++11
12 / 100
 100 ms 14392 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], 0 - dp[i-1][1].second} >= pair<int,int>{dp[i-1][0].first + v[i] - c, 0 - (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 92 ms 13960 KB Output is correct
2 Correct 95 ms 14216 KB Output is correct
3 Correct 100 ms 14376 KB Output is correct
4 Correct 98 ms 14288 KB Output is correct
5 Correct 85 ms 14204 KB Output is correct
6 Correct 87 ms 13968 KB Output is correct
7 Correct 93 ms 13912 KB Output is correct
8 Correct 99 ms 14240 KB Output is correct
9 Correct 94 ms 13996 KB Output is correct
10 Correct 89 ms 14028 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13984 KB Output is correct
2 Correct 61 ms 14368 KB Output is correct
3 Correct 54 ms 13928 KB Output is correct
4 Correct 96 ms 14160 KB Output is correct
5 Correct 54 ms 13976 KB Output is correct
6 Correct 47 ms 14024 KB Output is correct
7 Correct 88 ms 14392 KB Output is correct
8 Correct 61 ms 14236 KB Output is correct
9 Correct 66 ms 13932 KB Output is correct
10 Correct 91 ms 14280 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 13960 KB Output is correct
2 Correct 95 ms 14216 KB Output is correct
3 Correct 100 ms 14376 KB Output is correct
4 Correct 98 ms 14288 KB Output is correct
5 Correct 85 ms 14204 KB Output is correct
6 Correct 87 ms 13968 KB Output is correct
7 Correct 93 ms 13912 KB Output is correct
8 Correct 99 ms 14240 KB Output is correct
9 Correct 94 ms 13996 KB Output is correct
10 Correct 89 ms 14028 KB Output is correct
11 Correct 57 ms 13984 KB Output is correct
12 Correct 61 ms 14368 KB Output is correct
13 Correct 54 ms 13928 KB Output is correct
14 Correct 96 ms 14160 KB Output is correct
15 Correct 54 ms 13976 KB Output is correct
16 Correct 47 ms 14024 KB Output is correct
17 Correct 88 ms 14392 KB Output is correct
18 Correct 61 ms 14236 KB Output is correct
19 Correct 66 ms 13932 KB Output is correct
20 Correct 91 ms 14280 KB Output is correct
21 Incorrect 57 ms 14156 KB Output isn't correct
22 Halted 0 ms 0 KB -