Submission #719206

#TimeUsernameProblemLanguageResultExecution timeMemory
719206stevancvLottery (CEOI18_lot)C++14
100 / 100
476 ms8304 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e4 + 2; const int M = 100 + 2; const int inf = 1e9; int a[N], b[M], dp[2][N], ans[M][N], cnt[N], n, l, q, m; void Solve(int j) { int t = j & 1; for (int i = 0; i <= l; i++) cnt[i] = 0; for (int i = 0; i < m; i++) if (i != j) cnt[dp[t][i]]++; for (int i = 1; i <= l; i++) cnt[i] += cnt[i - 1]; for (int i = 0; i < q; i++) ans[i][j] = cnt[b[i]]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> l; m = n - l + 1; for (int i = 0; i < n; i++) cin >> a[i]; cin >> q; for (int i = 0; i < q; i++) cin >> b[i]; for (int i = 0; i < m; i++) for (int j = 0; j < l; j++) dp[0][i] += a[j] != a[i + j]; Solve(0); for (int i = 1; i < m; i++) { int t = i & 1; for (int j = 0; j < m; j++) dp[t][j] = 0; for (int j = 0; j < l; j++) dp[t][0] += a[i + j] != a[j]; for (int j = 1; j < m; j++) { dp[t][j] = dp[1 - t][j - 1]; dp[t][j] += (a[i + l - 1] != a[j + l - 1]) - (a[i - 1] != a[j - 1]); } Solve(i); } for (int i = 0; i < q; i++) { for (int j = 0; j < m; j++) cout << ans[i][j] << sp; cout << en; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...