Submission #556113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556113	2022-05-02T11:10:09 Z	HeatDroppa	Stove (JOI18_stove)	C++14	50 / 100	1000 ms	2260 KB

stove

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim=1e5+4;
const ll inf=1e18;
ll dp_new[lim];
ll dp_old[lim];
int t[lim];
int n,k;
void solve(int l,int r,int optl,int optr)
{
    int med=(l+r)>>1;
    pair<ll,int> bst={inf,-1};
    for(int i=optl;i<=min(med,optr);++i)
        bst=min(bst,{dp_old[i-1]+t[med]-t[i]+1,i});
    dp_new[med]=bst.first;
    if(l<med) solve(l,med-1,optl,bst.second);
    if(med<r) solve(med+1,r,bst.second,optr);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>t[i],
        dp_old[i]=t[i]-t[1]+1;
    for(int i=2;i<=k;++i)
        solve(i,n,i,n),
        swap(dp_old,dp_new);
    cout<<dp_old[n]<<'\n';
    return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	1808 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	2 ms	1876 KB	Output is correct
5	Correct	2 ms	1876 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct
7	Correct	2 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	1808 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	2 ms	1876 KB	Output is correct
5	Correct	2 ms	1876 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct
7	Correct	2 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	1876 KB	Output is correct
11	Correct	17 ms	1876 KB	Output is correct
12	Correct	167 ms	1892 KB	Output is correct
13	Correct	304 ms	1876 KB	Output is correct
14	Correct	337 ms	1876 KB	Output is correct
15	Correct	343 ms	1888 KB	Output is correct

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	1808 KB	Output is correct
3	Correct	1 ms	1876 KB	Output is correct
4	Correct	2 ms	1876 KB	Output is correct
5	Correct	2 ms	1876 KB	Output is correct
6	Correct	1 ms	1876 KB	Output is correct
7	Correct	2 ms	1876 KB	Output is correct
8	Correct	2 ms	1876 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	1876 KB	Output is correct
11	Correct	17 ms	1876 KB	Output is correct
12	Correct	167 ms	1892 KB	Output is correct
13	Correct	304 ms	1876 KB	Output is correct
14	Correct	337 ms	1876 KB	Output is correct
15	Correct	343 ms	1888 KB	Output is correct
16	Correct	39 ms	2260 KB	Output is correct
17	Correct	299 ms	2256 KB	Output is correct
18	Execution timed out	1085 ms	2260 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-