Approach
Sorting and greedy selection
For ABC323 C — World Tour Finals, 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
- 63 lines of C++ from the credited upstream file abc323_c.cpp.
- The implementation visibly relies on sequence storage.
- 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 <iostream>3#include <map>4#include <tuple>5#include <vector>6 7using namespace std;8 9int main() {10 unsigned long N = 0, M = 0;11 cin >> N >> M;12 13 vector<int> A(M, 0);14 for (unsigned long i = 0; i < M; i++) {15 cin >> A[i];16 }17 18 tuple<int, int> max_score = {0, 0};19 vector<tuple<int, vector<int>>> user; 20 for (unsigned long i = 0; i < N; i++) {21 string s = "";22 cin >> s;23 vector<int> not_ans;24 int score = int(i);25 for (unsigned long si = 0; si < s.size(); si++) {26 if (s[si] == 'x') {27 not_ans.push_back(A[si]);28 } else {29 score += A[si];30 }31 }32 33 sort(not_ans.rbegin(), not_ans.rend());34 user.push_back({score, not_ans});35 if (get<1>(max_score) < score) {36 max_score = {int(i), score};37 }38 }39 40 sort(A.rbegin(), A.rend());41 42 for (unsigned long i = 0; i < user.size(); i++) {43 if (int(i) == get<0>(max_score)) {44 cout << 0 << endl;45 continue;46 }47 48 int remain = get<1>(max_score) - get<0>(user[i]);49 int need_ans = 0;50 vector<int> not_ans_score = get<1>(user[i]);51 for (unsigned long nai = 0; nai < not_ans_score.size(); nai++) {52 if (remain <= 0) {53 break;54 }55 if (remain > 0) {56 need_ans++;57 }58 remain -= not_ans_score[nai];59 }60 61 cout << need_ans << endl;62 }63}