Advertisement
HabKaffee

mana1

Nov 15th, 2020
169
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.     int buff = 0, buff1 = 0;
  41.    
  42.     for (cnt = 1; cnt <= n; ++cnt) {
  43.         for (size_t i = 0; i < n - cnt; ++i){
  44.             size_t j = i + cnt;                
  45.             if (j > 0) {
  46.                 if (decisionVector[i][j-1].first == INT_MAX){
  47.                     buff = INT_MAX;
  48.                 }
  49.                 else {
  50.                     buff = abs(levelWithoutRepetitionOfMana[i].first - levelWithoutRepetitionOfMana[j].first) + decisionVector[i][j - 1].first;
  51.                 }
  52.                 if (decisionVector[i][j-1].second == INT_MAX){
  53.                     buff1 = INT_MAX;
  54.                 }
  55.                 else {
  56.                     buff1 = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[j - 1].first) + decisionVector[i][j - 1].second;
  57.                 }
  58.                
  59.                 decisionVector[i][j].second = std::min(buff, buff1);
  60.                 if (decisionVector[i][j].second > levelWithoutRepetitionOfMana[j].second)
  61.                     decisionVector[i][j].second = INT_MAX;
  62.             }
  63.             if (i + 1 < n) {
  64.                 if (decisionVector[i+1][j].first == INT_MAX){
  65.                     buff = INT_MAX;
  66.                 }
  67.                 else {
  68.                     buff = abs(levelWithoutRepetitionOfMana[i + 1].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].first;
  69.                 }
  70.                 if (decisionVector[i+1][j].second == INT_MAX){
  71.                     buff1 = INT_MAX;
  72.                 }
  73.                 else {
  74.                     buff1 = abs(levelWithoutRepetitionOfMana[j].first - levelWithoutRepetitionOfMana[i].first) + decisionVector[i + 1][j].second;
  75.                 }
  76.                 decisionVector[i][j].first = std::min(buff, buff1);
  77.                 if (decisionVector[i][j].first > levelWithoutRepetitionOfMana[i].second)
  78.                     decisionVector[i][j].first = INT_MAX;
  79.             }
  80.         }
  81.     }
  82.  
  83.     int result = std::min(decisionVector[0][n - 1].first, decisionVector[0][n - 1].second);
  84.     if (result == INT_MAX){
  85.         std::cout << -1 << std::endl;
  86.     }
  87.     else{
  88.         std::cout << result <<std::endl;
  89.     }
  90.     return 0;
  91. }
Advertisement
RAW Paste Data Copied
Advertisement