Submission #834279

#TimeUsernameProblemLanguageResultExecution timeMemory
834279unnickArcade (NOI20_arcade)C++14
65 / 100
1028 ms34008 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define ll long long int main(){ ios_base::sync_with_stdio(false); int n,m; cin >> n >> m; std::vector<ll> times; std::vector<ll> positions; for (int i = 0; i < m; i++) { ll tmp; cin >> tmp; times.push_back(tmp); } for (int i = 0; i < m; i++) { ll tmp; cin >> tmp; positions.push_back(tmp); } std::vector<int> idxes; for (int i = 0; i < m; i++) { idxes.push_back(i); } std::sort(idxes.begin(), idxes.end(), [times, positions](int ia, int ib){ ll sa = times[ia] + positions[ia]; ll sb = times[ib] + positions[ib]; return sa == sb ? times[ia] < times[ib] : sa < sb; }); std::vector<int> frontier; int num_arms = 0; for (int idx : idxes) { int selected_idx = -1; ll selected_score = 2100000000; for (int i = 0; i < num_arms; i++) { int idx2 = frontier[i]; // // cant press a button twice with one hand // if (positions[idx] == positions[idx2] && times[idx] == times[idx2]) continue; // check if we can reach the button if (positions[idx]-positions[idx2] > times[idx]-times[idx2]) continue; // use the "least useful" hand if (selected_score < positions[idx2]-times[idx2]) continue; // cout << idx2 << " is better\n"; selected_score = positions[idx2]-times[idx2]; selected_idx = i; } if (selected_idx == -1) { // cout << "pushed" << "\n"; frontier.push_back(idx); num_arms++; } else { // cout << "replaced " << selected_idx << "\n"; frontier[selected_idx] = idx; } // cout << "frontier: "; // for (int i : frontier) { // cout << i << " "; // } // cout << "\n"; } cout << num_arms << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...