Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct TSubject
- {
- __int64 a, b;
- int nmb, c;
- } sb[100];
- bool operator < (const TSubject &x, const TSubject &y)
- {
- return x.c < y.c;
- }
- int n, m, k, cur = 0;
- __int64 d[50][101][51];
- pair<int, int> p[50][101][51], state;
- int main()
- {
- cin >> n >> m >> k;
- for (int i = 0; i < m; ++i)
- {
- cin >> sb[i].a >> sb[i].b >> sb[i].c;
- sb[i].nmb = i + 1;
- }
- sort(sb, sb + m);
- state = make_pair(0, 0);
- for (int i = 0; i < m; ++i)
- for (int j = 0; j <= sb[i].b - sb[i].a; ++j)
- {
- d[i][j][1] = sb[i].a + j;
- for (int z = 2; z <= n; ++z)
- {
- d[i][j][z] = -1;
- for (int last = i - 1; last >= 0; --last)
- if (sb[last].c < sb[i].c)
- for (int t = 0; t <= 1; ++t)
- {
- __int64 temp = sb[i].a + j;
- bool yes = (t == 0) ? temp % k == 0 : temp >= k;
- temp = (t == 0) ? temp / k : temp - k;
- temp -= sb[last].a;
- if (!yes) continue;
- if (temp >= 0 && temp <= sb[last].b - sb[last].a
- && d[last][temp][z - 1] != -1
- && d[last][temp][z - 1] + sb[i].a + j > d[i][j][z])
- {
- d[i][j][z] = d[last][temp][z - 1] + sb[i].a + j;
- p[i][j][z] = make_pair(last, temp);
- }
- }
- }
- if (d[i][j][n] > d[state.first][state.second][n])
- state = make_pair(i, j);
- }
- if (d[state.first][state.second][n] == -1)
- {
- cout << "NO";
- return 0;
- }
- vector<pair<int, __int64> > ans;
- for (int i = n; i >= 1; --i)
- {
- ans.push_back(make_pair(sb[state.first].nmb, sb[state.first].a + state.second));
- state = p[state.first][state.second][i];
- }
- cout << "YES" << endl;
- for (int i = n - 1; i >= 0; --i)
- cout << ans[i].first << ' ' << ans[i].second << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement