- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 71 lines of C++ from the credited upstream file abc167_c.cpp.
- The implementation visibly relies on sequence storage.
- 5 loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <tuple>4#include <vector>5 6using namespace std;7 8int count_ok(unsigned int x, vector<unsigned int> A) {9 int c = 0;10 for (unsigned int i = 1; i < A.size(); i++) {11 if (A[i] >= x) {12 c++;13 }14 }15 16 return c;17}18 19void rec_plus(vector<vector<unsigned int>> list, unsigned int x, unsigned int n,20 unsigned int m, unsigned int caidx, vector<unsigned int> now,21 int& ans) {22 if (count_ok(x, now) == int(m) && (ans < 0 || int(now[0]) < ans)) {23 ans = int(now[0]);24 return;25 };26 27 if (caidx == n) {28 return;29 }30 31 vector<unsigned int> added_now = now;32 for (unsigned int i = 0; i <= m; i++) {33 added_now[i] += list[caidx][i];34 }35 36 caidx++;37 rec_plus(list, x, n, m, caidx, now, ans);38 rec_plus(list, x, n, m, caidx, added_now, ans);39}40 41int main() {42 unsigned int n, m, x;43 cin >> n >> m >> x;44 45 vector<vector<unsigned int>> ca_list(n);46 vector<unsigned int> all(m + 1, 0);47 for (unsigned int ni = 0; ni < n; ni++) {48 vector<unsigned int> ca(m + 1, 0); 49 for (unsigned int mi = 0; mi < m + 1; mi++) {50 unsigned int c_or_a;51 cin >> c_or_a;52 ca[mi] = c_or_a;53 all[mi] += c_or_a;54 }55 ca_list[ni] = ca;56 }57 58 for (unsigned int ai = 1; ai < m; ai++) {59 if (all[ai] < x) {60 cout << "-1" << endl;61 return 0;62 }63 }64 65 int ans = -1;66 vector<unsigned int> now(m + 1, 0);67 rec_plus(ca_list, x, n, m, 0, now, ans);68 69 cout << ans << endl;70}71