oj.uz

Submission #595960

# Submission time Handle Problem Language Result Execution time Memory
595960 2022-07-14T08:21:39 Z Tenis0206 Feast (NOI19_feast) C++11
0 / 100
 107 ms 10872 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];

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++)
    {
        if(Max - sp[i] > Max_pref || (Max - sp[i]==Max_pref && nrval < nrval_pref))
        {
            Max_pref = Max - sp[i];
            nrval_pref = nrval;
        }
        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;
        }
    }
    return {Max,nrval};
}

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 = -oo;
    int dr = oo;
    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
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10508 KB Output is correct
2 Correct 26 ms 10244 KB Output is correct
3 Correct 26 ms 10024 KB Output is correct
4 Incorrect 50 ms 10064 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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