Advertisement
Josif_tepe

Untitled

Oct 31st, 2022
892
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5. struct kandelabra {
  6.     int pos, cost, rad;
  7. };
  8. int M, K;
  9. int n;
  10. kandelabra v[105];
  11. int dp[101][10005];
  12. bool visited[101][10001];
  13. int rec(int at, int k) {
  14.     if(at < 0) {
  15.         return 0;
  16.     }
  17.     if(k < 0) {
  18.         return 0;
  19.     }
  20.     if(dp[at][k] != -1) {
  21.         return dp[at][k];
  22.     }
  23.     int result1 = 0, result2 = 0, result = 0;
  24.     if(k - v[at].cost >= 0) {
  25.         int tmp = 0;
  26.         if(v[at].pos + v[at].rad <= M) {
  27.             tmp += v[at].rad;
  28.         }
  29.         else {
  30.             tmp += M - v[at].pos;
  31.         }
  32.         if(v[at].pos - v[at].rad >= 0) {
  33.             tmp += v[at].rad;
  34.         }
  35.         else {
  36.             tmp += v[at].pos;
  37.         }
  38.         result1 = rec(at - 1, k - v[at].cost) + tmp;
  39.     }
  40.     result2 = rec(at - 1, k);
  41.     if(result1 > result2) {
  42.         visited[at][k] = true;
  43.     }
  44.     result = max(result1, result2);
  45.    
  46.     return dp[at][k] = result;
  47. }
  48. int upaleni_kandelabri[100001];
  49. int main()
  50.  
  51. {
  52.     memset(dp, -1, sizeof dp);
  53.     memset(visited, false, sizeof visited);
  54.     memset(upaleni_kandelabri, 0, sizeof upaleni_kandelabri);
  55.     cin >> M >> K;
  56.     cin >> n;
  57.     for(int i = 0; i < n; i++) {
  58.         cin >> v[i].pos >> v[i].cost >> v[i].rad;
  59.     }
  60.    
  61.     cout << rec(n - 1, K) << " ";
  62.     for(int i = n - 1; i >= 0; i--) {
  63.         if(K >= 0) {
  64.             if(visited[i][K]) {
  65.                 for(int j = max(0, v[i].pos - v[i].rad); j <= min(M - 1, v[i].pos + v[i].rad - 1); j++) {
  66.                     upaleni_kandelabri[j] = 1;
  67.                 }
  68.                 K -= v[i].cost;
  69.             }
  70.         }
  71.     }
  72.     upaleni_kandelabri[0] = 1;
  73.     int result = 0;
  74.     for(int i = 1; i < M; i++) {
  75.         if(upaleni_kandelabri[i] == 0) {
  76.             upaleni_kandelabri[i] = upaleni_kandelabri[i - 1] + 1;
  77.             result = max(result, upaleni_kandelabri[i]);
  78.         }
  79.         else {
  80.             upaleni_kandelabri[i] = 0;
  81.         }
  82.         result = max(result, upaleni_kandelabri[i]);
  83.     }
  84.     cout << result << endl;
  85.     return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement