oj.uz

Submission #1102956

# Submission time Handle Problem Language Result Execution time Memory
1102956 2024-10-19T09:20:15 Z Tenis0206 Feast (NOI19_feast) C++11
0 / 100
 57 ms 14412 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 = 1;
    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
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14160 KB Output is correct
2 Correct 30 ms 14372 KB Output is correct
3 Correct 29 ms 14160 KB Output is correct
4 Incorrect 42 ms 14160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 14412 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 2556 KB Output is correct
2 Incorrect 1 ms 2384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2556 KB Output is correct
2 Incorrect 1 ms 2384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2556 KB Output is correct
2 Incorrect 1 ms 2384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

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