daily pastebin goal
48%
SHARE
TWEET

Untitled

a guest Jun 14th, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 5 * 1000 * 1000 + 17;
  5.  
  6. int nies = 1000 * 1000 * 1000 + 17;
  7.  
  8. int dp[N];
  9. bool tab[N];
  10. int pre[N];
  11.  
  12. int n, m, k, l;
  13.  
  14.  
  15. int main(){
  16.   ios_base::sync_with_stdio(false);
  17.   cin.tie(NULL);
  18.   cout.tie(NULL);
  19.  
  20.   cin >> n >> m >> k >> l;
  21.  
  22.   for(int i = 0; i < m; i++){
  23.     int pom;
  24.     cin >> pom;
  25.     tab[pom] = true;
  26.   }
  27.  
  28.   // cout << "PRE \n";
  29.   for(int i = 1; i <= n + k + l + 1; i++){
  30.     pre[i] = pre[i-1] + tab[i - 1];
  31.     dp[i] = nies;
  32.     // cout << pre[i] << " ";
  33.   }
  34.   // cout << "\n";
  35.   dp[1] = 0;
  36.  
  37.  
  38.   for(int i = 1; i <= n + k + l + 1; i++){
  39.     if( pre[i+k+l] - pre[i+k] == 0 ){
  40.       dp[i+k+l] = dp[i] + 1;
  41.     }
  42.     if(tab[i] == 0){
  43.       dp[i+1] = min(dp[i+1], dp[i]) ;
  44.     }
  45.   }
  46.  
  47.   // cout << "DP\n";
  48.   // for(int i = 1; i <= n + k + l; i++){
  49.   //   cout << dp[i] << " ";
  50.   // }
  51.   // cout << "\n";
  52.  
  53.   int odp = nies;
  54.   for(int i = n + 1; i <= n + k + l + 1; i++){
  55.     odp = min(odp, dp[i]);
  56.   }
  57.   if(odp >= nies){
  58.    cout <<  -1 << "\n";
  59.    return 0;
  60.   }
  61.   cout << odp << "\n";
  62.   return 0;
  63. }
  64.  
  65.  
  66.  /*
  67.  
  68. 13 4 3 3
  69. 3 7 8 13
  70. 3
  71.  
  72.  
  73. 7 4 1 2
  74. 2 5 6 7
  75. -1
  76.  
  77. 10 2 3 1
  78. 4 7
  79. 2
  80.  
  81.  
  82.  */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top