Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- // greedy choice:
- // always choose a optimal number, summing the largest initial score with the least final scores
- // gives an optimal solution
- // safe move:
- // choose a sum that is less or equal to the current score and move ahead if so.
- int naive(std::vector<unsigned int> initial_scores, std::vector<unsigned int> final_scores, int n) {
- auto max_score = final_scores[0] + initial_scores[n];
- n--;
- int score = n;
- for(int i = 1; i < final_scores.size(); i++) {
- auto cal = final_scores[i] + initial_scores[n];
- // the less value, the upper the player.
- if(cal <= max_score) {
- n--;
- score--;
- if(n < 0) {
- break;
- }
- }
- }
- // +1 because of the index.
- // +1 because the current index points to the number before the actual one.
- return score + 2;
- }
- int main() {
- std::vector<unsigned int> initial_scores;
- std::vector<unsigned int> final_scores;
- int count, n;
- std::cin >> count >> n;
- for(int i = 0; i < count; i++) {
- int t;
- std::cin >> t;
- initial_scores.push_back(t);
- }
- for(int i = 0; i < count; i++) {
- int t;
- std::cin >> t;
- final_scores.push_back(t);
- }
- std::cout<<naive(initial_scores, final_scores, n-1);
- return 0;
- }
Add Comment
Please, Sign In to add comment