oj.uz

답안 #1051050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051050 2024-08-09T18:54:48 Z pera 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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