oj.uz

Submission #242814

# Submission time Handle Problem Language Result Execution time Memory
242814 2020-06-29T10:47:43 Z gs18115 Feast (NOI19_feast) C++14
49 / 100
 1000 ms 160904 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
inline void clear(vector<ll>&v)
{
    v.clear();
    v.shrink_to_fit();
    return;
}
inline void merge(vector<ll>&rt,vector<ll>&l,vector<ll>&r)
{
    rt.clear();
    rt.eb(l[0]+r[0]);
    int li=1,ri=1;
    while(li<(int)l.size()&&ri<(int)r.size())
    {
        if(l[li]-l[li-1]>r[ri]-r[ri-1])
            rt.eb(rt.back()+l[li]-l[li-1]),li++;
        else
            rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
    }
    while(li<(int)l.size())
        rt.eb(rt.back()+l[li]-l[li-1]),li++;
    while(ri<(int)r.size())
        rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
    return;
}
inline void mx(vector<ll>&rt,vector<ll>&r)
{
    if(rt.size()<r.size())
        rt.resize(r.size(),-INF);
    for(int i=0;i<(int)r.size();i++)
        rt[i]=max(rt[i],r[i]);
    return;
}
vector<ll>no[1200010],l[1200010],r[1200010],lr[1200010];
void dnc(int n,int s,int e,vector<ll>&v)
{
    if(s==e)
    {
        no[n].eb(0);
        no[n].eb(v[s]);
        l[n].eb(v[s]);
        r[n].eb(v[s]);
        lr[n].eb(v[s]);
        return;
    }
    int m=s+(e-s)/2;
    dnc(n*2,s,m,v);
    dnc(n*2+1,m+1,e,v);
    vector<ll>v1,v2,v3,v4;
    merge(no[n],no[n*2],no[n*2+1]);
    merge(l[n],lr[n*2],l[n*2+1]);
    merge(r[n],r[n*2],lr[n*2+1]);
    merge(lr[n],lr[n*2],lr[n*2+1]);
    merge(v1,r[n*2],l[n*2+1]);
    merge(v2,l[n*2],no[n*2+1]);
    merge(v3,no[n*2],r[n*2+1]);
    merge(v4,l[n*2],r[n*2+1]);
    v1.insert(v1.begin(),-INF);
    v4.insert(v4.begin(),-INF);
    mx(no[n],v1);
    mx(l[n],v2);
    mx(r[n],v3);
    mx(lr[n],v4);
    for(int i=n*2;i<n*2+2;i++)
        clear(no[i]),clear(l[i]),clear(r[i]),clear(lr[i]);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<ll>v(n);
    for(ll&t:v)
        cin>>t;
    v.insert(v.begin(),0ll);
    dnc(1,1,n,v);
    ll ans=0;
    for(int i=0;i<=k;i++)
        ans=max(ans,no[1][i]);
    cout<<ans<<'\n';
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 160904 KB Output is correct
2 Execution timed out 1004 ms 160856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 158608 KB Output is correct
2 Correct 971 ms 159556 KB Output is correct
3 Correct 949 ms 159140 KB Output is correct
4 Correct 955 ms 158788 KB Output is correct
5 Correct 957 ms 160320 KB Output is correct
6 Correct 955 ms 159384 KB Output is correct
7 Correct 975 ms 158700 KB Output is correct
8 Correct 986 ms 160760 KB Output is correct
9 Correct 982 ms 160208 KB Output is correct
10 Correct 977 ms 158460 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 140276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 113144 KB Output is correct
2 Correct 66 ms 113020 KB Output is correct
3 Correct 65 ms 113144 KB Output is correct
4 Correct 70 ms 113056 KB Output is correct
5 Correct 65 ms 113016 KB Output is correct
6 Correct 65 ms 113016 KB Output is correct
7 Correct 67 ms 113016 KB Output is correct
8 Correct 65 ms 113016 KB Output is correct
9 Correct 64 ms 113016 KB Output is correct
10 Correct 75 ms 113016 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 113144 KB Output is correct
2 Correct 66 ms 113020 KB Output is correct
3 Correct 65 ms 113144 KB Output is correct
4 Correct 70 ms 113056 KB Output is correct
5 Correct 65 ms 113016 KB Output is correct
6 Correct 65 ms 113016 KB Output is correct
7 Correct 67 ms 113016 KB Output is correct
8 Correct 65 ms 113016 KB Output is correct
9 Correct 64 ms 113016 KB Output is correct
10 Correct 75 ms 113016 KB Output is correct
11 Correct 75 ms 113144 KB Output is correct
12 Correct 66 ms 113272 KB Output is correct
13 Correct 69 ms 113144 KB Output is correct
14 Correct 65 ms 113144 KB Output is correct
15 Correct 67 ms 113144 KB Output is correct
16 Correct 68 ms 113144 KB Output is correct
17 Correct 66 ms 113144 KB Output is correct
18 Correct 67 ms 113144 KB Output is correct
19 Correct 70 ms 113144 KB Output is correct
20 Correct 73 ms 113144 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 113144 KB Output is correct
2 Correct 66 ms 113020 KB Output is correct
3 Correct 65 ms 113144 KB Output is correct
4 Correct 70 ms 113056 KB Output is correct
5 Correct 65 ms 113016 KB Output is correct
6 Correct 65 ms 113016 KB Output is correct
7 Correct 67 ms 113016 KB Output is correct
8 Correct 65 ms 113016 KB Output is correct
9 Correct 64 ms 113016 KB Output is correct
10 Correct 75 ms 113016 KB Output is correct
11 Correct 75 ms 113144 KB Output is correct
12 Correct 66 ms 113272 KB Output is correct
13 Correct 69 ms 113144 KB Output is correct
14 Correct 65 ms 113144 KB Output is correct
15 Correct 67 ms 113144 KB Output is correct
16 Correct 68 ms 113144 KB Output is correct
17 Correct 66 ms 113144 KB Output is correct
18 Correct 67 ms 113144 KB Output is correct
19 Correct 70 ms 113144 KB Output is correct
20 Correct 73 ms 113144 KB Output is correct
21 Correct 70 ms 113400 KB Output is correct
22 Correct 73 ms 113404 KB Output is correct
23 Correct 72 ms 113272 KB Output is correct
24 Correct 70 ms 113272 KB Output is correct
25 Correct 82 ms 113272 KB Output is correct
26 Correct 71 ms 113272 KB Output is correct
27 Correct 70 ms 113272 KB Output is correct
28 Correct 72 ms 113272 KB Output is correct
29 Correct 71 ms 113304 KB Output is correct
30 Correct 72 ms 113272 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 160904 KB Output is correct
2 Execution timed out 1004 ms 160856 KB Time limit exceeded
3 Halted 0 ms 0 KB -