Submission #523664

#TimeUsernameProblemLanguageResultExecution timeMemory
523664boykutMarriage questions (IZhO14_marriage)C++14
68 / 100
1599 ms235236 KiB
#include <bits/stdc++.h> using namespace std; //char dp[2222][33333]; int pref[2002][30003]; int n, m, k; int check(int l, int r) { if (r - l + 1 < m) return 0; for (int j = 1; j <= m; j++) { if (pref[j][r] - pref[j][l-1] == 0) return 0; } return 1; } 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; pref[b][a] = 1; } for (int j = 1; j <= m; j++) { for (int i = 1; i <= n; i++) { pref[j][i] += pref[j][i-1]; } } int ans = 0; for (int l = 1, r = 1; l <= n; l++) { while (r <= n && check(l, r) == 0) r++; if (r <= n) { ans += n - r + 1; } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...