답안 #556055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556055	2022-05-02T09:27:51 Z	HeatDroppa	Stove (JOI18_stove)	C++14	50 / 100	1000 ms	3628 KB

stove

#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;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	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

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	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

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	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	-