oj.uz

Submission #556108

# Submission time Handle Problem Language Result Execution time Memory
556108 2022-05-02T11:07:43 Z HeatDroppa Stove (JOI18_stove) C++14
50 / 100
 1000 ms 3268 KB 
#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)
{
    if(l>r) return ;
    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;
    solve(l,med-1,optl,bst.second);
    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 1 ms 212 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 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 1 ms 312 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 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 1 ms 312 KB Output is correct
10 Correct 4 ms 1876 KB Output is correct
11 Correct 18 ms 1876 KB Output is correct
12 Correct 173 ms 1908 KB Output is correct
13 Correct 326 ms 1896 KB Output is correct
14 Correct 345 ms 1892 KB Output is correct
15 Correct 376 ms 1892 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 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 1 ms 312 KB Output is correct
10 Correct 4 ms 1876 KB Output is correct
11 Correct 18 ms 1876 KB Output is correct
12 Correct 173 ms 1908 KB Output is correct
13 Correct 326 ms 1896 KB Output is correct
14 Correct 345 ms 1892 KB Output is correct
15 Correct 376 ms 1892 KB Output is correct
16 Correct 62 ms 3204 KB Output is correct
17 Correct 324 ms 3268 KB Output is correct
18 Execution timed out 1095 ms 3148 KB Time limit exceeded
19 Halted 0 ms 0 KB -