SHARE
TWEET

Untitled

a guest Oct 20th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. const int maxN = 1000;
  6. const int inf = 1e9 + 20;
  7.  
  8. int cnt;
  9. std::vector<std::pair<int, int>> vec;
  10. int dp[maxN][maxN][2], was[maxN][maxN][2];
  11.  
  12. int get(int left, int right, int pos) {
  13.     if (left == right) {
  14.         return 0;
  15.     }
  16.     if (was[left][right][pos]) return dp[left][right][pos];
  17.     was[left][right][pos] = 1;
  18.     int& ans = dp[left][right][pos];
  19.     if (pos == 0) {
  20.         auto leftAns = get(left + 1, right, 0) + vec[left + 1].first - vec[left].first;
  21.         auto rightAns = get(left + 1, right, 1) + vec[right].first - vec[left].first;  
  22.         if (leftAns <= vec[left].second) {
  23.             ans = std::min(ans, leftAns);
  24.         }
  25.         if (rightAns <= vec[right].second) {
  26.             ans = std::min(ans, rightAns);
  27.         }
  28.     } else {
  29.         auto leftAns = get(left, right - 1, 0) + vec[right].first - vec[left].first;
  30.         auto rightAns = get(left, right - 1, 1) + vec[right].first - vec[right - 1].first; 
  31.         if (leftAns <= vec[right].second) {
  32.             ans = std::min(ans, leftAns);
  33.         }
  34.         if (rightAns <= vec[right].second) {
  35.             ans = std::min(ans, rightAns);
  36.         }
  37.     }
  38.     return ans;
  39. }
  40.  
  41. int main() {
  42.     std::ios::sync_with_stdio(0);
  43.     std::cin.tie(0);
  44.     std::cout.tie(0);
  45.     std::cin >> cnt;
  46.     vec.resize(cnt);
  47.     for (int i = 0; i < cnt; i++) {
  48.         int dist, time;
  49.         std::cin >> dist >> time;
  50.         vec[i] = {dist, time};
  51.     }
  52.     std::sort(vec.begin(), vec.end());
  53.     for (int i = 0; i < cnt; i++)
  54.         for (int j = 0; j < cnt; j++) {
  55.             dp[i][j][0] = dp[i][j][1] = inf;
  56.         }
  57.     auto ans = std::min(get(0, cnt - 1, 0), get(0, cnt - 1, 1));
  58.     if (ans < inf) {
  59.         std::cout << ans;
  60.     } else {
  61.         std::cout << "No solution";
  62.     }
  63.     return 0;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top