SHARE
TWEET

Education Reform

Serega Oct 16th, 2011 342 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. struct TSubject
  6. {
  7.         __int64 a, b;
  8.         int nmb, c;
  9. } sb[100];
  10. bool operator < (const TSubject &x, const TSubject &y)
  11. {
  12.         return x.c < y.c;
  13. }
  14. int n, m, k, cur = 0;
  15. __int64 d[50][101][51];
  16. pair<int, int> p[50][101][51], state;
  17. int main()
  18. {
  19.         cin >> n >> m >> k;
  20.         for (int i = 0; i < m; ++i)
  21.         {
  22.                 cin >> sb[i].a >> sb[i].b >> sb[i].c;
  23.                 sb[i].nmb = i + 1;
  24.         }
  25.         sort(sb, sb + m);
  26.         state = make_pair(0, 0);
  27.         for (int i = 0; i < m; ++i)
  28.                 for (int j = 0; j <= sb[i].b - sb[i].a; ++j)
  29.                 {
  30.                         d[i][j][1] = sb[i].a + j;
  31.                         for (int z = 2; z <= n; ++z)
  32.                         {
  33.                                 d[i][j][z] = -1;
  34.                                 for (int last = i - 1; last >= 0; --last)
  35.                                         if (sb[last].c < sb[i].c)
  36.                                                 for (int t = 0; t <= 1; ++t)
  37.                                                 {
  38.                                                         __int64 temp = sb[i].a + j;
  39.                                                         bool yes = (t == 0) ? temp % k == 0 : temp >= k;
  40.                                                         temp = (t == 0) ? temp / k : temp - k;
  41.                                                         temp -= sb[last].a;
  42.                                                         if (!yes) continue;
  43.                                                         if (temp >= 0 && temp <= sb[last].b - sb[last].a
  44.                                                                 && d[last][temp][z - 1] != -1
  45.                                                                 && d[last][temp][z - 1] + sb[i].a + j > d[i][j][z])
  46.                                                         {
  47.                                                                 d[i][j][z] = d[last][temp][z - 1] + sb[i].a + j;
  48.                                                                 p[i][j][z] = make_pair(last, temp);
  49.                                                         }
  50.                                                 }
  51.                         }
  52.                         if (d[i][j][n] > d[state.first][state.second][n])
  53.                                 state = make_pair(i, j);
  54.                 }
  55.         if (d[state.first][state.second][n] == -1)
  56.         {
  57.                 cout << "NO";
  58.                 return 0;
  59.         }
  60.         vector<pair<int, __int64> > ans;
  61.         for (int i = n; i >= 1; --i)
  62.         {
  63.                 ans.push_back(make_pair(sb[state.first].nmb, sb[state.first].a + state.second));
  64.                 state = p[state.first][state.second][i];
  65.         }
  66.         cout << "YES" << endl;
  67.         for (int i = n - 1; i >= 0; --i)
  68.                 cout << ans[i].first << ' ' << ans[i].second << endl;
  69.         return 0;
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top