Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstring>
- using namespace std;
- struct kandelabra {
- int pos, cost, rad;
- };
- int M, K;
- int n;
- kandelabra v[105];
- int dp[101][10005];
- bool visited[101][10001];
- int rec(int at, int k) {
- if(at < 0) {
- return 0;
- }
- if(k < 0) {
- return 0;
- }
- if(dp[at][k] != -1) {
- return dp[at][k];
- }
- int result1 = 0, result2 = 0, result = 0;
- if(k - v[at].cost >= 0) {
- int tmp = 0;
- if(v[at].pos + v[at].rad <= M) {
- tmp += v[at].rad;
- }
- else {
- tmp += M - v[at].pos;
- }
- if(v[at].pos - v[at].rad >= 0) {
- tmp += v[at].rad;
- }
- else {
- tmp += v[at].pos;
- }
- result1 = rec(at - 1, k - v[at].cost) + tmp;
- }
- result2 = rec(at - 1, k);
- if(result1 > result2) {
- visited[at][k] = true;
- }
- result = max(result1, result2);
- return dp[at][k] = result;
- }
- int upaleni_kandelabri[100001];
- int main()
- {
- memset(dp, -1, sizeof dp);
- memset(visited, false, sizeof visited);
- memset(upaleni_kandelabri, 0, sizeof upaleni_kandelabri);
- cin >> M >> K;
- cin >> n;
- for(int i = 0; i < n; i++) {
- cin >> v[i].pos >> v[i].cost >> v[i].rad;
- }
- cout << rec(n - 1, K) << " ";
- for(int i = n - 1; i >= 0; i--) {
- if(K >= 0) {
- if(visited[i][K]) {
- for(int j = max(0, v[i].pos - v[i].rad); j <= min(M - 1, v[i].pos + v[i].rad - 1); j++) {
- upaleni_kandelabri[j] = 1;
- }
- K -= v[i].cost;
- }
- }
- }
- upaleni_kandelabri[0] = 1;
- int result = 0;
- for(int i = 1; i < M; i++) {
- if(upaleni_kandelabri[i] == 0) {
- upaleni_kandelabri[i] = upaleni_kandelabri[i - 1] + 1;
- result = max(result, upaleni_kandelabri[i]);
- }
- else {
- upaleni_kandelabri[i] = 0;
- }
- result = max(result, upaleni_kandelabri[i]);
- }
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement