oj.uz

Submission #1090568

# Submission time Handle Problem Language Result Execution time Memory
1090568 2024-09-18T12:58:51 Z hoangnguyenh K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 1764 KB 
#include<bits/stdc++.h>
#define ll long long
#define el '\n'
#define rep(i,a,b) for (int i=a;i<=b;++i)
using namespace std;
ll n,k,a[100001],dp[101][100001],ma[22][100001];
ll get(ll l, ll r)
{
    if (l>r) return 1e18;
    ll k=log2(r-l+1);
    return max(ma[k][l],ma[k][r-(1<<k)+1]);
}
void sol(ll g, ll l, ll r, ll ol, ll oR)
{
    if (l>r) return;
    ll mid=l+r>>1;
    dp[g][mid]=1e18;
    ll pos=0;
    rep(i,1,mid)
    {
        ll newcost=dp[g-1][i]+get(i+1,mid);
        //if (g==2 && mid==6) cout<<ol<<' '<<oR<<' '<<dp[g-1][i]<<' '<<get(i+1,mid)<<' '<<i+1<<el;
        if (dp[g][mid]>newcost)
        {
            pos=i;
            dp[g][mid]=newcost;
        }
    }
    sol(g,l,mid-1,ol,pos);
    sol(g,mid+1,r,pos,oR);
}
void solve()
{
    cin>>n>>k;
    rep(i,1,k) dp[0][i]=1e18;
    rep(i,1,n)
    {
        cin>>a[i];
        ma[0][i]=a[i];
    }
    for (int i=1;i<=log2(n);i++)
    {
        for (int j=1;j<=(n-(1<<i)+1);j++) ma[i][j]=max(ma[i-1][j],ma[i-1][j+(1<<(i-1))]);
    }
    rep(i,1,n)
    {
        dp[1][i]=get(1,i);
    }
    rep(i,2,k) sol(i,1,n,1,n);
    cout<<dp[k][n];
}
int main()
{
    
    solve();
    return 0;
}

Compilation message

blocks.cpp: In function 'void sol(long long int, long long int, long long int, long long int, long long int)':
blocks.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 444 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 440 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 444 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 4 ms 600 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 1 ms 448 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 0 ms 352 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 2 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 5 ms 1116 KB Output is correct
54 Correct 6 ms 1116 KB Output is correct
55 Correct 3 ms 604 KB Output is correct
56 Correct 5 ms 1116 KB Output is correct
57 Correct 6 ms 924 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 440 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 444 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 4 ms 600 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 1 ms 448 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 0 ms 352 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 2 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 5 ms 1116 KB Output is correct
54 Correct 6 ms 1116 KB Output is correct
55 Correct 3 ms 604 KB Output is correct
56 Correct 5 ms 1116 KB Output is correct
57 Correct 6 ms 924 KB Output is correct
58 Execution timed out 1067 ms 1764 KB Time limit exceeded
59 Halted 0 ms 0 KB -