| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 556055 |
2022-05-02T09:27:51 Z |
HeatDroppa |
Stove (JOI18_stove) |
C++14 |
|
1000 ms |
3628 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll lim=1e5+4;
const ll inf=1e18;
vector<ll> dp_new;
vector<ll> dp_old;
ll t[lim];
ll n,k;
ll cost(ll l,ll r)
{
return t[r]+1-t[l];
}
void solve(ll l,ll r,ll optl,ll optr)
{
if(l>r) return ;
ll med=(l+r)>>1;
pair<ll,ll> bst={inf,-1};
for(ll i=optl;i<=min(med,optr);++i)
bst=min(bst,{dp_old[i-1]+cost(i,med),i});
ll opt=bst.second;
dp_new[med]=bst.first;
solve(l,med-1,optl,opt);
solve(med+1,r,opt,optr);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
dp_new.resize(n+2,0);
dp_old.resize(n+2,0);
for(ll i=1;i<=n;++i)
cin>>t[i];
for(ll i=1;i<=n;++i)
dp_old[i]=cost(1,i);
for(ll i=2;i<=k;++i)
solve(1,n,1,n),
swap(dp_old,dp_new);
cout<<dp_old[n]<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
7 ms |
340 KB |
Output is correct |
| 12 |
Correct |
72 ms |
416 KB |
Output is correct |
| 13 |
Correct |
114 ms |
432 KB |
Output is correct |
| 14 |
Correct |
141 ms |
420 KB |
Output is correct |
| 15 |
Correct |
145 ms |
416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
7 ms |
340 KB |
Output is correct |
| 12 |
Correct |
72 ms |
416 KB |
Output is correct |
| 13 |
Correct |
114 ms |
432 KB |
Output is correct |
| 14 |
Correct |
141 ms |
420 KB |
Output is correct |
| 15 |
Correct |
145 ms |
416 KB |
Output is correct |
| 16 |
Correct |
26 ms |
3544 KB |
Output is correct |
| 17 |
Correct |
156 ms |
3628 KB |
Output is correct |
| 18 |
Execution timed out |
1079 ms |
3576 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
