oj.uz

Submission #1102957

# Submission time Handle Problem Language Result Execution time Memory
1102957 2024-10-19T09:21:33 Z Tenis0206 Feast (NOI19_feast) C++11
18 / 100
 43 ms 9820 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5;

int n,k;
int v[nmax + 5], sp[nmax + 5];

pair<int,int> dp[nmax + 5];

pair<int,int> calculate(int c)
{
    pair<int,int> Max = {0, 0};
    dp[0] = {0, 0};
    for(int i=1;i<=n;i++)
    {
        dp[i] = dp[i - 1];
        if(Max.first + sp[i] - c > dp[i].first || (Max.first + sp[i] - c == dp[i].first && Max.second + 1 < dp[i].second))
        {
            dp[i].first = Max.first + sp[i] - c;
            dp[i].second = Max.second + 1;
        }
        if(dp[i].first - sp[i] > Max.first || (dp[i].first - sp[i] == Max.first && dp[i].second < Max.second))
        {
            Max.first = dp[i].first - sp[i];
            Max.second = dp[i].second;
        }
    }
    return dp[n];
}

int solve()
{
    int st = 1;
    int dr = 1e14;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        pair<int,int> val = calculate(mij);
        if(val.second == k)
        {
            return val.first + k * mij;
        }
        if(val.second < k)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    pair<int,int> val = calculate(st);
    return val.first + k * st;
}

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];
    }
    cout<<solve()<<'\n';
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 9552 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 9552 KB Output is correct
2 Correct 26 ms 9648 KB Output is correct
3 Correct 24 ms 9552 KB Output is correct
4 Incorrect 41 ms 9664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9552 KB Output is correct
2 Correct 36 ms 9528 KB Output is correct
3 Correct 42 ms 9524 KB Output is correct
4 Correct 34 ms 9572 KB Output is correct
5 Correct 35 ms 9704 KB Output is correct
6 Correct 35 ms 9744 KB Output is correct
7 Correct 35 ms 9808 KB Output is correct
8 Correct 41 ms 9544 KB Output is correct
9 Correct 40 ms 9820 KB Output is correct
10 Correct 36 ms 9808 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #7
0 / 29.0

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