Guest User

Untitled

a guest
Sep 24th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. // greedy choice:
  6. // always choose a optimal number, summing the largest initial score with the least final scores
  7. // gives an optimal solution
  8. // safe move:
  9. // choose a sum that is less or equal to the current score and move ahead if so.
  10. int naive(std::vector<unsigned int> initial_scores, std::vector<unsigned int> final_scores, int n) {
  11. auto max_score = final_scores[0] + initial_scores[n];
  12. n--;
  13. int score = n;
  14.  
  15. for(int i = 1; i < final_scores.size(); i++) {
  16. auto cal = final_scores[i] + initial_scores[n];
  17. // the less value, the upper the player.
  18. if(cal <= max_score) {
  19. n--;
  20. score--;
  21. if(n < 0) {
  22. break;
  23. }
  24. }
  25. }
  26.  
  27. // +1 because of the index.
  28. // +1 because the current index points to the number before the actual one.
  29. return score + 2;
  30. }
  31.  
  32. int main() {
  33. std::vector<unsigned int> initial_scores;
  34. std::vector<unsigned int> final_scores;
  35.  
  36. int count, n;
  37. std::cin >> count >> n;
  38.  
  39. for(int i = 0; i < count; i++) {
  40. int t;
  41. std::cin >> t;
  42.  
  43. initial_scores.push_back(t);
  44. }
  45.  
  46. for(int i = 0; i < count; i++) {
  47. int t;
  48. std::cin >> t;
  49. final_scores.push_back(t);
  50. }
  51.  
  52. std::cout<<naive(initial_scores, final_scores, n-1);
  53. return 0;
  54. }
Add Comment
Please, Sign In to add comment