oj.uz

Submission #1035943

# Submission time Handle Problem Language Result Execution time Memory
1035943 2024-07-26T20:06:15 Z pera K blocks (IZhO14_blocks) C++17
0 / 100
 1 ms 2496 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1 , K = 1e2 + 1 , LOG = 18;
int n , k , a[N] , mx[N][LOG] , dp[N] , ndp[N];
int GET(int L , int R){
   int sz = __lg(R - L + 1);
   return max(mx[L][sz] , mx[R - (1 << sz) + 1][sz]);
}
void solve(int l , int r , int L , int R){
   if(l > r){
      return;
   }
   int m = (l + r) / 2 , id;
   dp[m] = -1;
   for(int x = L;x <= min(m , R);x ++){
      if(dp[m] == -1 || dp[m] > ndp[x - 1] + GET(x , m)){
         dp[m] = ndp[x - 1] + GET(x , m);
         id = x;
      }
   }
   solve(l , m - 1 , L , id);
   solve(m + 1 , r , id , R);
}
int main(){
   cin >> n >> k;
   int _mx = 0;
   dp[0] = 1e9;
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
      _mx = max(_mx , a[i]);
      dp[i] =_mx;
      mx[i][0] = a[i];
   }
   for(int bit = 1;bit < LOG;bit ++){
      for(int i = 1;i + (1 << bit) - 1 <= n;i ++){
         mx[i][bit] = max(mx[i][bit - 1] , mx[i + (1 << (bit - 1))][bit - 1]);
      }
   }
   for(int x = 1;x < k;x ++){
      for(int x = 0;x <= n;x ++){
         ndp[x] = dp[x];
      }
      solve(1 , n , 1 , n);
   }
   cout << dp[n] << endl;
}

Compilation message

blocks.cpp: In function 'void solve(int, int, int, int)':
blocks.cpp:21:9: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |    solve(l , m - 1 , L , id);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2496 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Incorrect 1 ms 2396 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Halted 0 ms 0 KB -