oj.uz

Submission #558557

# Submission time Handle Problem Language Result Execution time Memory
558557 2022-05-07T14:16:40 Z stefantaga Feast (NOI19_feast) C++14
12 / 100
 1000 ms 10728 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n,i,k;
ll v[300005],din[300005],cnt[300005],sum[300005];
ll suma(int st,int dr)
{
    return sum[dr]-sum[st-1];
}
ll ok (ll mij)
{
    deque <int> st;
    st.push_back(0);
    for (i=1; i<=n; i++)
    {
        din[i]=din[i-1];
        cnt[i]=cnt[i-1];
        if (din[i]<din[i-1]+mij)
        {
            din[i]=din[i-1]+mij;
            cnt[i]=cnt[i-1]+1;
        }
        if (st.empty())
        {
            if (din[i]<v[i]+din[i-1]+mij)
            {
                din[i]=v[i]+din[i-1]+mij;
                cnt[i]=1+cnt[i-1];
            }
        }
        else
        {
            if (din[i]<din[st.front()]+suma(st.front()+1,i)+mij)
            {
                din[i]=din[st.front()]+suma(st.front()+1,i)+mij;
                cnt[i]=1+cnt[st.front()];
            }
        }
        while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
        {
            st.pop_back();
        }
        st.push_back(i);
    }
    return cnt[n];
}
ll st,dr,sol;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n>>k;
    for (i=1; i<=n; i++)
    {
        cin>>v[i];
        sum[i]=sum[i-1]+v[i];
    }
    st=-1e9;
    dr=1e9;
    int nr=200;
    for (;nr--;)
    {
        ll mij = (st+dr)/2;
        auto salut = ok(mij);
        if (salut>=k)
        {
            sol=mij;
            dr=mij;
        }
        else
        {
            st=mij;
        }
    }
    auto salut = ok(0);
    deque <int> st;
    st.push_back(0);
    for (i=1; i<=n; i++)
    {
        din[i]=din[i-1];
        cnt[i]=cnt[i-1];
        if (din[i]<din[i-1]+sol)
        {
            din[i]=din[i-1]+sol;
            cnt[i]=cnt[i-1]+1;
        }
        if (st.empty())
        {
            if (din[i]<v[i]+din[i-1]+sol)
            {
                din[i]=v[i]+din[i-1]+sol;
                cnt[i]=1+cnt[i-1];
            }
        }
        else
        {
            int poz=st.front();
            if (din[i]<din[poz]+suma(poz+1,i)+sol)
            {
                din[i]=din[poz]+suma(poz+1,i)+sol;
                cnt[i]=1+cnt[poz];
            }
        }
        while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
        {
            st.pop_back();
        }
        st.push_back(i);
    }
    cout<<din[n]-cnt[n]*sol;
    return 0;
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:80:10: warning: unused variable 'salut' [-Wunused-variable]
   80 |     auto salut = ok(0);
      |          ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 9408 KB Output is correct
2 Correct 507 ms 9592 KB Output is correct
3 Correct 530 ms 9700 KB Output is correct
4 Correct 499 ms 9676 KB Output is correct
5 Correct 492 ms 9584 KB Output is correct
6 Correct 491 ms 9368 KB Output is correct
7 Correct 487 ms 9424 KB Output is correct
8 Correct 494 ms 9608 KB Output is correct
9 Correct 491 ms 9440 KB Output is correct
10 Correct 479 ms 9536 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 10216 KB Output is correct
2 Correct 568 ms 10728 KB Output is correct
3 Correct 558 ms 10556 KB Output is correct
4 Correct 478 ms 10668 KB Output is correct
5 Correct 514 ms 9420 KB Output is correct
6 Correct 572 ms 10568 KB Output is correct
7 Correct 486 ms 10676 KB Output is correct
8 Correct 538 ms 9648 KB Output is correct
9 Correct 521 ms 9392 KB Output is correct
10 Correct 494 ms 10284 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 9604 KB Time limit exceeded
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 Correct 490 ms 9408 KB Output is correct
2 Correct 507 ms 9592 KB Output is correct
3 Correct 530 ms 9700 KB Output is correct
4 Correct 499 ms 9676 KB Output is correct
5 Correct 492 ms 9584 KB Output is correct
6 Correct 491 ms 9368 KB Output is correct
7 Correct 487 ms 9424 KB Output is correct
8 Correct 494 ms 9608 KB Output is correct
9 Correct 491 ms 9440 KB Output is correct
10 Correct 479 ms 9536 KB Output is correct
11 Correct 570 ms 10216 KB Output is correct
12 Correct 568 ms 10728 KB Output is correct
13 Correct 558 ms 10556 KB Output is correct
14 Correct 478 ms 10668 KB Output is correct
15 Correct 514 ms 9420 KB Output is correct
16 Correct 572 ms 10568 KB Output is correct
17 Correct 486 ms 10676 KB Output is correct
18 Correct 538 ms 9648 KB Output is correct
19 Correct 521 ms 9392 KB Output is correct
20 Correct 494 ms 10284 KB Output is correct
21 Execution timed out 1014 ms 9604 KB Time limit exceeded
22 Halted 0 ms 0 KB -