Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<map>
- #include<climits>
- #include<algorithm>
- int main() {
- std::cin.tie(nullptr);
- std::ios_base::sync_with_stdio(false);
- size_t n = 0;
- std::cin >> n;
- std::vector<std::pair<int, int>> level(n);
- for (size_t i = 0; i < n; ++i) {
- std::cin >> level[i].first>>level[i].second; // first - position of mana; second - time of mana;
- }
- sort(level.begin(), level.end());
- std::vector<std::pair<int, int>> levelWithoutRepetitionOfMana;
- size_t cnt = 0;
- levelWithoutRepetitionOfMana.push_back(level[0]);
- for (size_t i = 0; i < n; ++i) {
- if (levelWithoutRepetitionOfMana[cnt].first == level[i].first){
- continue;
- }
- levelWithoutRepetitionOfMana.push_back(level[i]);
- cnt++;
- }
- n = levelWithoutRepetitionOfMana.size();
- std::vector<std::vector<std::pair<int, int>>> decisionVector(n, std::vector < std::pair<int,int>> (n, std::make_pair(0, 0)));
- int buff = 0, buff1 = 0;
- for (cnt = 1; cnt <= n; ++cnt) {
- for (size_t i = 0; i < n - cnt; ++i){
- size_t j = i + cnt;
- if (j > 0) {
- if (decisionVector[i][j-1].first == INT_MAX){
- buff = INT_MAX;
- }
- else {
- buff = abs(levelWithoutRepetitionOfMana[i].first - levelWithoutRepetitionOfMana[j].first) + decisionVector[i][j - 1].first;
- }
- if (decisionVector[i][j-1].second == INT_MAX){
- buff1 = INT_MAX;
- }
- else {
- buff1 = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[j - 1].first) + decisionVector[i][j - 1].second;
- }
- decisionVector[i][j].second = std::min(buff, buff1);
- if (decisionVector[i][j].second > levelWithoutRepetitionOfMana[j].second)
- decisionVector[i][j].second = INT_MAX;
- }
- if (i + 1 < n) {
- if (decisionVector[i+1][j].first == INT_MAX){
- buff = INT_MAX;
- }
- else {
- buff = abs(levelWithoutRepetitionOfMana[i + 1].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].first;
- }
- if (decisionVector[i+1][j].second == INT_MAX){
- buff1 = INT_MAX;
- }
- else {
- buff1 = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].second;
- }
- decisionVector[i][j].first = std::min(buff, buff1);
- if (decisionVector[i][j].first > levelWithoutRepetitionOfMana[i].second)
- decisionVector[i][j].first = INT_MAX;
- }
- }
- }
- int result = std::min(decisionVector[0][n - 1].first, decisionVector[0][n - 1].second);
- if (result == INT_MAX){
- std::cout << -1 << std::endl;
- }
- else{
- std::cout << result <<std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement