oj.uz

Submission #1051050

# Submission time Handle Problem Language Result Execution time Memory
1051050 2024-08-09T18:54:48 Z pera Watching (JOI13_watching) C++17
100 / 100
 609 ms 109916 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 = 29;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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 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 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 89436 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 1 ms 348 KB Output is correct
7 Correct 16 ms 89788 KB Output is correct
8 Correct 47 ms 90972 KB Output is correct
9 Correct 287 ms 98396 KB Output is correct
10 Correct 609 ms 109916 KB Output is correct
11 Correct 36 ms 90456 KB Output is correct
12 Correct 329 ms 100952 KB Output is correct
13 Correct 14 ms 89692 KB Output is correct
14 Correct 16 ms 89692 KB Output is correct
15 Correct 14 ms 89804 KB Output is correct