oj.uz

Submission #1051048

# Submission time Handle Problem Language Result Execution time Memory
1051048 2024-08-09T18:53:51 Z pera Watching (JOI13_watching) C++17
0 / 100
 8 ms 89436 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 1;
int n , p , q;
int dp[N][N][3][2] , best[N][N];
//prefix , # of used w , [NO , i -> i + t , i - t -> i] , [w , 2w];
vector<int> A(N);
int main(){
   cin >> n >> p >> q;
   for(int i = 1;i <= n;i ++){
      cin >> A[i];
   }
   if(p + q >= n){
      cout << 1 << endl;
      return 0;
   }
   sort(A.begin() , A.begin() + n + 1);
   int ans = 0;
   for(int bit = 20;bit >= 0;bit --){
      ans ^= (1 << bit);
      for(int i = 0;i <= n;i ++){
         for(int j = 0;j <= p;j ++){
            best[i][j] = 1e9;
            for(int x = 0;x < 3;x ++){
               for(int y = 0;y < 2;y ++){
                  dp[i][j][x][y] = 1e9;
               }
            }
         }
      }
      for(int x = 0;x <= p;x ++){
         dp[0][x][0][0] = 0;
         best[0][x] = 0;
      }
      int o = 1 , e = 1;
      for(int i = 1;i <= n;i ++){
         while(A[i] - A[o] + 1 > ans){
            ++o;
         }
         while(A[i] - A[e] + 1 > 2 * ans){
            ++e;
         }
         assert(0 < min(o , e) && max(o , e) <= n);
         for(int j = 0;j <= p;j ++){
            if(o != i){
               dp[i][j][0][0] = dp[o][j][1][0];
            }
            if(e != i){
               dp[i][j][0][0] = min(dp[i][j][0][0] , dp[e][j][1][1]);
            }
            if(j > 0){
               dp[i][j][1][0] = best[i - 1][j - 1];
            }
            dp[i][j][1][1] = best[i - 1][j] + 1;
            if(j > 0){
               dp[i][j][2][0] = best[o - 1][j - 1];
            }
            dp[i][j][2][1] = best[e - 1][j] + 1;
         }
         for(int j = 0;j <= p;j ++){
            for(int x = 0;x < 3;x ++){
               for(int y = 0;y < 2;y ++){
                  best[i][j] = min(best[i][j] , dp[i][j][x][y]);
               }
            }
         }
      }
      if(best[n][p] <= q){
         ans ^= (1 << bit);
      }
   }
   cout << ++ans << endl;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 89436 KB Output isn't correct
2 Halted 0 ms 0 KB -