Please help! Acmp, how do we solve it?
-
https://acmp.ru/index.asp?main=task&id_task=638
All Russian Olympics on informatics
(Time: 1 seq.) Remembrance: 16 Mb Complex: 37%
2127. It has been years since the first All-Russian Olympiad on Informatics. Like many other competitions, our Olympics now take place a few days. Now, even the task of choosing the right time for olimpiads is a challenge. The different planets of the Russian Federation use different means of calculating time: the length of the month, the number of days per week and the days on which the olympiads cannot be held may differ. There was a need to write a programme that would help to meet that challenge. And then the jury will remember that we've already foreseeed this situation and offered you this task.
As a first step, find a number of ways to choose the time of the Olympics.
Input data
In the first line of INPUT entry file. TXT contains two whole numbers n and k (1 < k < n < 100000), the number of days and the duration of the Olympics, respectively. In the second line, the number of days per week w, the number of days prohibited weekly, dw and the day of the week, which is the first day of the month s (1 ≤ s ≤ w ≤ n, 0 ≤ dw ≤ w). The third line contains dw days of the week (e.g. weekends) in which olympiad cannot be held. The fourth line lists the number of days dm not suitable for Olympics for reasons other than the weekly order (e.g. public holidays). The last line contains dm full numbers, the numbers of these days. The days of the month are also numbered from 1. We note that some days may be prohibited for both reasons.
Output data
The OUTPUT exit file. TXT release the only whole number - the number of ways to choose k consecutive days to which Olympics may be held.
Here's my code:
#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;
}
-
It's simple. ♪ ♪ We're gonna go for a head.
#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;
}
