Submission #523660

#TimeUsernameProblemLanguageResultExecution timeMemory
523660boykutMarriage questions (IZhO14_marriage)C++14
62 / 100
1601 ms262148 KiB
#include <bits/stdc++.h> using namespace std; char dp[2001][30001]; int pref[2001][30001]; int n, m, k; int check(int l, int r) { if (r - l + 1 < m) return 0; vector<int> mas(m + 1, 0); for (int j = 1; j <= m; j++) { if (pref[j][r] - pref[j][l-1] > 0) mas[j] = 1; } return (count(mas.begin(), mas.end(), 0) == 1 ? 1 : 0); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0; i < k; i++) { int a, b; cin >> a >> b; dp[b][a] = 1; } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { pref[j][i] = pref[j][i-1] + dp[j][i]; } } long long ans = 0; for (int l = 1, r = 1; l <= n; l++) { while (r <= n && !check(l, r)) r++; if (r <= n) { ans += n - r + 1; } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...