Advertisement
ThegeekKnight16

Ticket Inspector

Apr 26th, 2023
1,081
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 610;
  4. const int MAXK = 60;
  5. int dp[MAXN][MAXK];
  6. int s[MAXN][MAXN];
  7. int last[MAXN][MAXK];
  8. int N, K;
  9.  
  10. int cost(int ini, int fim)
  11. {
  12.     return s[fim][N] - s[fim][fim] - s[ini-1][N] + s[ini-1][fim];
  13. }
  14.  
  15. int main()
  16. {
  17.     ios_base::sync_with_stdio(false);
  18.     cin.tie(NULL);
  19.     cin >> N >> K;
  20.     for (int i = 1; i < N; i++)
  21.     {
  22.         for (int j = i+1; j <= N; j++)
  23.         {
  24.             cin >> s[i][j];
  25.         }
  26.     }
  27.  
  28.     for (int i = 1; i <= N; i++)
  29.     {
  30.         for (int j = 1; j <= N; j++)
  31.         {
  32.             s[i][j] += s[i][j-1] + s[i-1][j];
  33.             s[i][j] -= s[i-1][j-1];
  34.             // cerr << s[i][j] << " ";
  35.         }
  36.         // cerr << '\n';
  37.     }
  38.  
  39.  
  40.     for (int j = 1; j <= K; j++)
  41.     {
  42.         for (int i = 1; i < N; i++)
  43.         {
  44.             if (j == 1) {dp[i][j] = s[i][N] - s[i][i]; continue;}
  45.             for (int k = 1; k < i; k++)
  46.             {
  47.                 // cerr << "||" << cost(k+1, i) << '\n';
  48.                 if (dp[k][j-1] + cost(k+1, i) > dp[i][j])
  49.                 {
  50.                     last[i][j] = k;
  51.                     dp[i][j] = dp[k][j-1] + cost(k+1, i);
  52.                 }
  53.             }
  54.         }
  55.     }
  56.  
  57.     // for (int i = 1; i < N; i++) cerr << dp[i][K] << " ";
  58.     // cerr << '\n';
  59.     int x = 0;
  60.     for (int i = 1; i < N; i++)
  61.     {
  62.         if (dp[i][K] > dp[x][K]) x = i;
  63.     }
  64.  
  65.     vector<int> resp;
  66.  
  67.     while (K)
  68.     {
  69.         resp.push_back(x);
  70.         x = last[x][K];
  71.         K--;
  72.     }
  73.  
  74.     reverse(resp.begin(), resp.end());
  75.     // resp.pop_back();
  76.  
  77.     for (auto x : resp) cout << x << " ";
  78.  
  79. }
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement