oj.uz

Submission #1043220

# Submission time Handle Problem Language Result Execution time Memory
1043220 2024-08-04T05:03:03 Z 0pt1mus23 K blocks (IZhO14_blocks) C++14
0 / 100
 11 ms 42588 KB 
#pragma GCC optimize("O3", "inline")

#include <bits/stdc++.h> 
using namespace std; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define ins insert
#define pb push_back
// #define int long long int
#define pii pair<int, int>
#define endl '\n' 
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
#define hash z0hashp
#define div  z0dvp
const int mod = 1e9 +7, sze = 1e5 +23, inf = INT_MAX, P = 1453;
int dp[sze][101];

int arr[sze];

const int LOG = 20;
int dpt[LOG+1][sze];
int lg[sze];
void opt1z(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        dpt[0][i-1]=arr[i];
    }
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;

    for(int i =2;i<=n;i++){
        lg[i]=lg[i/2]+1;
    }
    for(int i = 1;i<LOG;i++){
        for(int j=0;j + (1<<i)<=n;j++){
            dpt[i][j]=max(dpt[i-1][j],dpt[i-1][j + (1<<(i-1))]);
        }
    }
    auto qry = [](int lx,int rx) -> int{
        lx--;
        rx--;   
        int ix = lg[rx-lx+1];
        return max(dpt[ix][lx],dpt[ix][rx - (1<<ix) +1]);
    };


    for(int i=1;i<=n;i++){
        for(int  j=1;j<=k;j++){
            int mx = arr[i];
            int ip= i;
            int lx =k;
            int rx = i;
            while(lx<=rx){
                int mid = (lx+rx)/2;
                int x = qry(mid,i);
                if(x<=arr[i]){
                    ip = mid;
                    rx=mid-1;
                }
                else{
                    lx=mid+1;
                }
            }
            dp[i][j]=dp[ip-1][j-1]+arr[i];
        }
    }

    drop(dp[n][k]);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Compilation message

blocks.cpp: In function 'void opt1z()':
blocks.cpp:52:17: warning: unused variable 'mx' [-Wunused-variable]
   52 |             int mx = arr[i];
      |                 ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42584 KB Output is correct
2 Incorrect 9 ms 42588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 42588 KB Output is correct
2 Incorrect 10 ms 42588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42584 KB Output is correct
2 Incorrect 9 ms 42588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42584 KB Output is correct
2 Incorrect 9 ms 42588 KB Output isn't correct
3 Halted 0 ms 0 KB -