Approach
Sorting and greedy selection
For ABC190 C — Bowls and Dishes, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 78 lines of C++ from the credited upstream file abc190_c.cpp.
- The implementation visibly relies on sequence storage, ordered lookup.
- 5 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
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 <cmath>3#include <iostream>4#include <map>5#include <vector>6 7using namespace std;8 9void gen(vector<vector<unsigned int>>& choices,10 vector<vector<unsigned int>>& balls_list, vector<unsigned int> balls,11 map<unsigned int, bool> selected, unsigned int pos) {12 if (pos == choices.size()) {13 balls_list.push_back(balls);14 return;15 }16 17 if (selected[choices[pos][0]] && selected[choices[pos][1]]) {18 gen(choices, balls_list, balls, selected, pos + 1);19 return;20 }21 22 if (!selected[choices[pos][0]]) {23 vector<unsigned int> tmp_balls = balls;24 tmp_balls.push_back(choices[pos][0]);25 map<unsigned int, bool> tmp_selected = selected;26 tmp_selected[choices[pos][0]] = true;27 gen(choices, balls_list, tmp_balls, tmp_selected, pos + 1);28 }29 30 if (!selected[choices[pos][1]]) {31 vector<unsigned int> tmp_balls = balls;32 tmp_balls.push_back(choices[pos][1]);33 map<unsigned int, bool> tmp_selected = selected;34 tmp_selected[choices[pos][1]] = true;35 gen(choices, balls_list, tmp_balls, tmp_selected, pos + 1);36 }37}38 39int main() {40 unsigned int n, m;41 cin >> n >> m;42 43 vector<vector<unsigned int>> conds(n + 1, vector<unsigned int>(n + 1, 0));44 for (unsigned int i = 0; i < m; i++) {45 unsigned int a, b;46 cin >> a >> b;47 conds[a][b]++;48 }49 50 unsigned int k;51 cin >> k;52 53 vector<vector<unsigned int>> choices(k, vector<unsigned int>(2, 0));54 for (unsigned int i = 0; i < k; i++) {55 cin >> choices[i][0] >> choices[i][1];56 }57 58 vector<vector<unsigned int>> balls_list;59 vector<unsigned int> balls;60 map<unsigned int, bool> selected;61 gen(choices, balls_list, balls, selected, 0);62 63 unsigned int ans = 0;64 for (auto& b : balls_list) {65 sort(b.begin(), b.end());66 unsigned int tmp_ans = 0;67 for (unsigned int i = 0; i < b.size(); i++) {68 for (unsigned int j = i + 1; j < b.size(); j++) {69 tmp_ans += conds[b[i]][b[j]];70 }71 }72 73 ans = max(ans, tmp_ans);74 }75 76 cout << ans << endl;77 return 0;78}