oj.uz

Submission #595967

# Submission time Handle Problem Language Result Execution time Memory
595967 2022-07-14T08:23:39 Z Tenis0206 Feast (NOI19_feast) C++11
4 / 100
 91 ms 10280 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++)
    {
        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;
        }
    }
    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;
    int rez = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        pair<int,int> val = get_val(mij);
        if(val.second<=k)
        {
            rez = max(rez, val.first + k * mij);
        }
        if(val.second<k)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    pair<int,int> val = get_val(st);
    rez = max(rez,val.first + k * st);
    cout<<rez<<'\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9292 KB Output is correct
2 Correct 44 ms 10196 KB Output is correct
3 Correct 49 ms 10280 KB Output is correct
4 Correct 50 ms 10204 KB Output is correct
5 Correct 45 ms 10192 KB Output is correct
6 Correct 45 ms 9980 KB Output is correct
7 Correct 45 ms 10004 KB Output is correct
8 Correct 44 ms 10188 KB Output is correct
9 Correct 53 ms 10076 KB Output is correct
10 Correct 47 ms 10156 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9292 KB Output is correct
2 Correct 44 ms 10196 KB Output is correct
3 Correct 49 ms 10280 KB Output is correct
4 Correct 50 ms 10204 KB Output is correct
5 Correct 45 ms 10192 KB Output is correct
6 Correct 45 ms 9980 KB Output is correct
7 Correct 45 ms 10004 KB Output is correct
8 Correct 44 ms 10188 KB Output is correct
9 Correct 53 ms 10076 KB Output is correct
10 Correct 47 ms 10156 KB Output is correct
11 Incorrect 36 ms 9476 KB Output isn't correct
12 Halted 0 ms 0 KB -