Advertisement
HabKaffee

mana

Nov 15th, 2020
139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<climits>
  5. #include<algorithm>
  6.  
  7.  
  8.  
  9. int main() {
  10.     std::cin.tie(nullptr);
  11.     std::ios_base::sync_with_stdio(false);
  12.  
  13.     size_t n = 0;
  14.     std::cin >> n;
  15.     std::vector<std::pair<int, int>> level(n);
  16.  
  17.     for (size_t i = 0; i < n; ++i) {
  18.         std::cin >> level[i].first>>level[i].second; // first - position of mana; second - time of mana;
  19.     }
  20.  
  21.     sort(level.begin(), level.end());
  22.  
  23.     std::vector<std::pair<int, int>> levelWithoutRepetitionOfMana;
  24.  
  25.     size_t cnt = 0;
  26.  
  27.     levelWithoutRepetitionOfMana.push_back(level[0]);
  28.  
  29.     for (size_t i = 0; i < n; ++i) {
  30.         if (levelWithoutRepetitionOfMana[cnt].first == level[i].first){
  31.             continue;
  32.         }
  33.         levelWithoutRepetitionOfMana.push_back(level[i]);
  34.         cnt++;
  35.     }
  36.  
  37.     n = levelWithoutRepetitionOfMana.size();
  38.     std::vector<std::vector<std::pair<int, int>>> decisionVector(n, std::vector < std::pair<int,int>> (n, std::make_pair(0, 0)));
  39.    
  40.    
  41.     for (cnt = 1; cnt <= n; ++cnt) {
  42.         for (size_t i = 0; i < n - cnt; ++i){
  43.             size_t j = i + cnt;                
  44.             if (j > 0) {
  45.                 if (decisionVector[i][j-1].first == INT_MAX){
  46.                     decisionVector[i][j-1].first = INT_MAX;
  47.                 }
  48.                 else {
  49.                     decisionVector[i][j-1].first = abs(levelWithoutRepetitionOfMana[i].first - levelWithoutRepetitionOfMana[j].first) + decisionVector[i][j - 1].first;
  50.                 }
  51.                 if (decisionVector[i][j-1].second == INT_MAX){
  52.                     decisionVector[i][j-1].second = INT_MAX;
  53.                 }
  54.                 else {
  55.                     decisionVector[i][j - 1].second = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[j - 1].first) + decisionVector[i][j - 1].second;
  56.                 }
  57.                 decisionVector[i][j].second = std::min(decisionVector[i][j-1].first, decisionVector[i][j-1].second);
  58.                 if (decisionVector[i][j].second > levelWithoutRepetitionOfMana[j].second)
  59.                     decisionVector[i][j].second = INT_MAX;
  60.             }
  61.             if (i + 1 < n) {
  62.                 if (decisionVector[i+1][j].first == INT_MAX){
  63.                     decisionVector[i+1][j].first = INT_MAX;
  64.                 }
  65.                 else {
  66.                     decisionVector[i+1][j].first = abs(levelWithoutRepetitionOfMana[i + 1].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].first;
  67.                 }
  68.                 if (decisionVector[i+1][j].second == INT_MAX){
  69.                     decisionVector[i+1][j].second = INT_MAX;
  70.                 }
  71.                 else {
  72.                     decisionVector[i+1][j].second = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].second;
  73.                 }
  74.                 decisionVector[i][j].first = std::min(decisionVector[i + 1][j].first, decisionVector[i + 1][j].second);
  75.                 if (decisionVector[i][j].first > levelWithoutRepetitionOfMana[i].second)
  76.                     decisionVector[i][j].first = INT_MAX;
  77.             }
  78.         }
  79.     }
  80.  
  81.     int result = std::min(decisionVector[0][n - 1].first, decisionVector[0][n - 1].second);
  82.     if (result == INT_MAX){
  83.         std::cout << -1 << std::endl;
  84.     }
  85.     else{
  86.         std::cout << result<<std::endl;
  87.     }
  88. }
Advertisement
RAW Paste Data Copied
Advertisement