Advertisement
Guest User

Untitled

a guest
Jun 14th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  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. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement