Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- const int maxN = 1000;
- const int inf = 1e9 + 20;
- int cnt;
- std::vector<std::pair<int, int>> vec;
- int dp[maxN][maxN][2], was[maxN][maxN][2];
- int get(int left, int right, int pos) {
- if (left == right) {
- return 0;
- }
- if (was[left][right][pos]) return dp[left][right][pos];
- was[left][right][pos] = 1;
- int& ans = dp[left][right][pos];
- if (pos == 0) {
- auto leftAns = get(left + 1, right, 0) + vec[left + 1].first - vec[left].first;
- auto rightAns = get(left + 1, right, 1) + vec[right].first - vec[left].first;
- if (leftAns <= vec[left].second) {
- ans = std::min(ans, leftAns);
- }
- if (rightAns <= vec[right].second) {
- ans = std::min(ans, rightAns);
- }
- } else {
- auto leftAns = get(left, right - 1, 0) + vec[right].first - vec[left].first;
- auto rightAns = get(left, right - 1, 1) + vec[right].first - vec[right - 1].first;
- if (leftAns <= vec[right].second) {
- ans = std::min(ans, leftAns);
- }
- if (rightAns <= vec[right].second) {
- ans = std::min(ans, rightAns);
- }
- }
- return ans;
- }
- int main() {
- std::ios::sync_with_stdio(0);
- std::cin.tie(0);
- std::cout.tie(0);
- std::cin >> cnt;
- vec.resize(cnt);
- for (int i = 0; i < cnt; i++) {
- int dist, time;
- std::cin >> dist >> time;
- vec[i] = {dist, time};
- }
- std::sort(vec.begin(), vec.end());
- for (int i = 0; i < cnt; i++)
- for (int j = 0; j < cnt; j++) {
- dp[i][j][0] = dp[i][j][1] = inf;
- }
- auto ans = std::min(get(0, cnt - 1, 0), get(0, cnt - 1, 1));
- if (ans < inf) {
- std::cout << ans;
- } else {
- std::cout << "No solution";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement