Submission #1005657

#TimeUsernameProblemLanguageResultExecution timeMemory
1005657anangoOlympiads (BOI19_olympiads)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> cons; int n,k,c; vector<int> getbest(vector<int> indices) { //get the best team using radix sort greedy method (the first k are the best team, rest are reserves) for (int i=0; i<k; i++) { for (int j=i+1; j<indices.size(); j++) { if (cons[indices[j]][i]>cons[indices[i]][i]) { swap(indices[i], indices[j]); } } } return indices; } int evaluate_combination(vector<int> indices) { vector<int> maxes(k,0); for (int i=0; i<indices.size(); i++) { for (int j=0; j<k; j++) { maxes[j]=max(maxes[j],cons[indices[i]][j]); } } return accumulate(maxes.begin(), maxes.end(), (int)0); } signed main() { freopen("input.txt","r", stdin); freopen("output.txt","w",stdout); cin >> n >> k >> c; vector<int> start; vector<int> totalmaxes(k,0); for (int i=0; i<n; i++) { start.push_back(i); vector<int> c1; for (int j=0; j<k; j++) { int x; cin >> x; c1.push_back(x); totalmaxes[j]=max(totalmaxes[j],x); } cons.push_back(c1); } int total = accumulate(totalmaxes.begin(), totalmaxes.end(), (int)0); start = getbest(start); priority_queue<vector<vector<int>>> current; current.push({{total},{0},start}); int ct=0; while (ct<c) { ct++; assert(current.size()>0); vector<vector<int>> latest = current.top(); current.pop(); int value = latest[0][0]; vector<int> indices = latest[2]; /*cout << ct <<" " << value << " " << latest[1][0] << endl; cout << "INDICES "; for (auto j:indices) { cout << j <<" "; } cout << endl;*/ if (ct==c) { cout << value << endl; return 0; } if (indices.size()==k) { //leaf node continue; } for (int nex=latest[1][0]; nex<k; nex++) { //the next optimal element being removed vector<int> new_indices(indices.begin(), indices.end()); //remove this position from the team new_indices.erase(find(new_indices.begin(),new_indices.end(),new_indices[nex])); new_indices = getbest(new_indices); current.push({{evaluate_combination(new_indices)},{nex},new_indices}); } } }

Compilation message (stderr)

olympiads.cpp: In function 'std::vector<int> getbest(std::vector<int>)':
olympiads.cpp:11:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int j=i+1; j<indices.size(); j++) {
      |                         ~^~~~~~~~~~~~~~~
olympiads.cpp: In function 'int evaluate_combination(std::vector<int>)':
olympiads.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0; i<indices.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:73:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |         if (indices.size()==k) {
      |             ~~~~~~~~~~~~~~^~~
olympiads.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen("input.txt","r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...