Submission #1051050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051050		pera	Watching (JOI13_watching)	C++17	100 / 100	609 ms	109916 KiB

watching

#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 / 50
• Subtask 2: 50 / 50