Submission #523663

#TimeUsernameProblemLanguageResultExecution timeMemory
523663boykutMarriage questions (IZhO14_marriage)C++14
68 / 100
1602 ms243904 KiB
#include <bits/stdc++.h> using namespace std; //char dp[2222][33333]; int pref[2222][33333]; 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]; } } 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...