Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <stdio.h>
- #include <algorithm>
- int main() {
- // Открываем файлы:
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- // Читаем данные:
- int count_trees;
- scanf("%d", &count_trees);
- std::vector<int> w(count_trees), e(count_trees);
- for (int i = 0; i < count_trees; ++i)
- scanf("%d %d", &w[i], &e[i]);
- int count_pos;
- scanf("%d", &count_pos);
- std::vector<int> x(count_pos);
- for (auto & it : x)
- scanf("%d", &it);
- // Решаем задачу двумерным ДП:
- std::vector<std::vector<int>> max(count_pos, std::vector<int>(count_trees, 1));
- for (int last_pos = 1; last_pos < count_pos; ++last_pos)
- for (int last_tree = 0; last_tree < count_trees; ++last_tree)
- for (int prev_pos = 0; prev_pos < last_pos; ++prev_pos)
- for (int prev_tree = 0; prev_tree < count_trees; ++prev_tree) {
- if (
- x[prev_pos] + e[prev_tree] <= x[last_pos] &&
- x[prev_pos] + w[last_tree] <= x[last_pos] &&
- max[last_pos][last_tree] <= max[prev_pos][prev_tree]
- )
- max[last_pos][last_tree] = max[prev_pos][prev_tree]+1;
- }
- // Выводим ответ: максимум среди элементов последнего столбца (последней клумбы)?
- printf("%d", *max_element(max.back().begin(), max.back().end()));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement