Прошу помочь! Задача на acmp, как решить ее?638
Всероссийская олимпиада по информатике
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
2127 год. Прошло уже много лет с тех пор, как состоялась первая Всероссийская олимпиада по информатике. Как и многие другие соревнования, наши олимпиады теперь проводятся в несколько дней. Теперь даже задача выбора подходящего времени для олимпиады представляет определенные трудности. Ведь на разных планетах, входящих в состав Российской Федерации используются разные способы отсчета времени: длина месяца, количество дней в неделе и те дни, по которым невозможно проведение олимпиады, могут различаться. Возникла необходимость написания программы, которая поможет решить эту задачу. И тогда в жюри вспомнят, что уже сейчас мы предвидели такую ситуацию и предложили вам решить подобную задачу.
В качестве первого шага найдите количество способов выбрать время проведения олимпиады.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа n и k (1 ≤ k ≤ n ≤ 100000) - количество дней месяца и продолжительность олимпиады соответственно. Во второй строке задаются количество дней в неделе w, количество дней, запрещенных еженедельно, dw и день недели, на который приходится первый день месяца s (1 ≤ s ≤ w ≤ n, 0 ≤ dw ≤ w). Третья строка содержит dw номеров дней недели (например, выходных), в которые нельзя проводить олимпиаду. В четвертой строке записано количество дней месяца dm, не подходящих для проведения олимпиады по причинам отличным от еженедельного распорядка (например, такими днями являются государственные праздники). Последняя строка содержит dm целых чисел - номера этих дней. Дни месяца так же нумеруются начиная с 1. Заметим, что некоторые дни могут быть запрещенными сразу по обеим причинам.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число - количество способов выбрать k подряд идущих дней, в которые возможно проведение олимпиады.
вот мой код:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
long long n,k,g,count,sum = 0;
cin >> n >> k;
vector <vector <long long>> dp(n + 1,vector<long long> (2, 0));
long long w, nt, s, ch = 1, unid;
cin >> w >> nt >> s;
count = s;
for(int i = 0; i < n; i++)
{
dp[i][1] = count;
if(count == w)
{count = 0;}
count++;
}
for(int i = 0; i < nt; i++)
{
cin >> unid;
for(int z = 0; z < n; z += ch)
{
if(dp[z][1] == unid)
{
dp[z][0] = -1;
ch = w;
}
}
}
ch = 1;
cin >> g;
for(int i = 0; i < g; i++)
{
cin >> unid;
dp[unid - 1][0] = -1;
}
int last = 0;
for(int i = 0; i < n; i++)
{
if(i + k > n){break;}
if(dp[i][0] == -1){continue;}
if(dp[i + k - 1][0] == -1){ i = i + k - 1;continue;}
dp[i][0] = dp[i][0] + last + 1;
last = dp[i][0];
}
int res = 0;
for(int i = 0; i < n; i++)
{
if(res < dp[i][0]){res = dp[i][0];}
}
cout << res << endl;
}
Ответы (1 шт):
Да все просто... Решаем "в лоб".
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int k,n,w,dw,s;
cin >> n >> k;
vector<int> v(n+1,1);
cin >> w >> dw >> s;
for(int j = 0; j < dw; ++j)
{
int d; cin >> d; int i = d - s + 1;
while(i < 1) i += w;
while(i > w) i -= w;
for(; i <= n; i += w) v[i] = 0;
}
cin >> dw;
for(int j = 0; j < dw; ++j)
{
int d; cin >> d;
v[d] = 0;
}
int cnt = 0;
w = 0;
for(int i = 1; i <= n; ++i)
{
if (v[i]) {
++w;
if (w >= k) cnt++;
}
else w = 0;
}
cout << cnt;
}