Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 5 * 1000 * 1000 + 17;
- int nies = 1000 * 1000 * 1000 + 17;
- int dp[N];
- bool tab[N];
- int pre[N];
- int n, m, k, l;
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- cin >> n >> m >> k >> l;
- for(int i = 0; i < m; i++){
- int pom;
- cin >> pom;
- tab[pom] = true;
- }
- // cout << "PRE \n";
- for(int i = 1; i <= n + k + l + 1; i++){
- pre[i] = pre[i-1] + tab[i - 1];
- dp[i] = nies;
- // cout << pre[i] << " ";
- }
- // cout << "\n";
- dp[1] = 0;
- for(int i = 1; i <= n + k + l + 1; i++){
- if( pre[i+k+l] - pre[i+k] == 0 ){
- dp[i+k+l] = dp[i] + 1;
- }
- if(tab[i] == 0){
- dp[i+1] = min(dp[i+1], dp[i]) ;
- }
- }
- // cout << "DP\n";
- // for(int i = 1; i <= n + k + l; i++){
- // cout << dp[i] << " ";
- // }
- // cout << "\n";
- int odp = nies;
- for(int i = n + 1; i <= n + k + l + 1; i++){
- odp = min(odp, dp[i]);
- }
- if(odp >= nies){
- cout << -1 << "\n";
- return 0;
- }
- cout << odp << "\n";
- return 0;
- }
- /*
- 13 4 3 3
- 3 7 8 13
- 3
- 7 4 1 2
- 2 5 6 7
- -1
- 10 2 3 1
- 4 7
- 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement