oj.uz

Submission #558556

# Submission time Handle Problem Language Result Execution time Memory
558556 2022-05-07T14:15:34 Z stefantaga Feast (NOI19_feast) C++14
12 / 100
 1000 ms 12616 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 504 ms 12208 KB Output is correct
2 Correct 503 ms 12396 KB Output is correct
3 Correct 508 ms 12576 KB Output is correct
4 Correct 502 ms 12488 KB Output is correct
5 Correct 506 ms 12544 KB Output is correct
6 Correct 506 ms 12236 KB Output is correct
7 Correct 483 ms 12216 KB Output is correct
8 Correct 510 ms 12500 KB Output is correct
9 Correct 532 ms 12284 KB Output is correct
10 Correct 519 ms 12372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 11248 KB Output is correct
2 Correct 594 ms 11848 KB Output is correct
3 Correct 568 ms 11660 KB Output is correct
4 Correct 496 ms 11672 KB Output is correct
5 Correct 553 ms 12236 KB Output is correct
6 Correct 625 ms 11672 KB Output is correct
7 Correct 483 ms 11852 KB Output is correct
8 Correct 576 ms 12512 KB Output is correct
9 Correct 609 ms 12188 KB Output is correct
10 Correct 551 ms 11488 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 12616 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 328 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 328 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 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 12208 KB Output is correct
2 Correct 503 ms 12396 KB Output is correct
3 Correct 508 ms 12576 KB Output is correct
4 Correct 502 ms 12488 KB Output is correct
5 Correct 506 ms 12544 KB Output is correct
6 Correct 506 ms 12236 KB Output is correct
7 Correct 483 ms 12216 KB Output is correct
8 Correct 510 ms 12500 KB Output is correct
9 Correct 532 ms 12284 KB Output is correct
10 Correct 519 ms 12372 KB Output is correct
11 Correct 578 ms 11248 KB Output is correct
12 Correct 594 ms 11848 KB Output is correct
13 Correct 568 ms 11660 KB Output is correct
14 Correct 496 ms 11672 KB Output is correct
15 Correct 553 ms 12236 KB Output is correct
16 Correct 625 ms 11672 KB Output is correct
17 Correct 483 ms 11852 KB Output is correct
18 Correct 576 ms 12512 KB Output is correct
19 Correct 609 ms 12188 KB Output is correct
20 Correct 551 ms 11488 KB Output is correct
21 Execution timed out 1064 ms 12616 KB Time limit exceeded
22 Halted 0 ms 0 KB -