oj.uz

Submission #1071078

# Submission time Handle Problem Language Result Execution time Memory
1071078 2024-08-23T04:14:06 Z sitablechair K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e5+3;
const ll INF=1e17;
int n,k,op[N][103],a[N],st[N][20];
ll f[N][103];
void pre() {
    For(i,1,n) st[i][0]=a[i];
    for(int j=1;j<=16;j++)
        for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
int get(int l,int r) {
    int len=__lg(r-l+1);
    return max(st[l][len],st[r-(1<<len)+1][len]);
}
void solve(int k,int l,int r,int lo,int hi) {
    if (l>r) return;
    int mid=l+r>>1;
    pair<ll,int> optimal={INF,-1};
    For(i,lo,min(mid,hi)) optimal=min(optimal,mpa(f[i-1][k-1]+get(i,mid),i));
    //if (k==2 && mid==n) debug(optimal.ss,f[3-1][k-1]);
    f[mid][k]=optimal.ff;
    solve(k,l,mid-1,lo,optimal.ss);
    solve(k,mid+1,r,optimal.ss,hi);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    For(i,1,n) cin >> a[i];
    pre();
    For(i,0,k)
        For(j,0,n) f[i][j]=INF;
    f[0][0]=0;
    For(i,1,k) solve(i,1,n,1,n);
    cout << f[n][k];
    return 0;
}

Compilation message

blocks.cpp: In function 'void pre()':
blocks.cpp:35:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |         for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
      |                                                                         ~^~
blocks.cpp: In function 'void solve(int, int, int, int, int)':
blocks.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -