Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Олимпиадные задачи
- // Задача B. Еловая алея
- // ibelyaev: 25Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.html
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- struct fir {
- int W,E;
- };
- vector<fir> firs;
- vector<int> beds;
- int n,m;
- vector<int> dp,amount;
- void input(){
- scanf("%d", &n);
- firs.resize(n);
- for (int i=0;i<n;++i)
- scanf("%d %d", &firs[i].W, &firs[i].E);
- scanf("%d", &m);
- beds.resize(m);
- for (int i=0;i<m;++i)
- scanf("%d", &beds[i]);
- dp.resize(m,-1);
- amount.resize(m);
- }
- void solve(){
- int minE = 0;
- for (int i=0;i<firs.size();++i) {
- if (firs[i].E < firs[minE].E)
- minE = i;
- }
- dp[0] = minE;
- amount[0] = 1;
- for (int i=1;i<beds.size();++i) {
- int bestF = -1;
- int maxAmount = 0;
- for (int j=i-1;j>=0;--j) {
- if (dp[j] != -1 && beds[j] + firs[dp[j]].E <= beds[i]) {
- for (int k=0;k<firs.size();++k) {
- if (beds[j] <= beds[i] - firs[k].W) {
- if (amount[j] > maxAmount) {
- maxAmount = amount[j];
- bestF = k;
- }
- if (amount[j] == maxAmount && firs[k].E < firs[bestF].E) {
- bestF = k;
- }
- }
- }
- }
- }
- if (bestF == -1) {
- dp[i] = minE;
- amount[i] = 1;
- }
- else {
- dp[i] = bestF;
- amount[i] = maxAmount + 1;
- }
- }
- }
- void output() {
- int pos = max_element(amount.begin(), amount.end()) - amount.begin();
- printf("%d\n", amount[pos]);
- stack<pair<int,int> > ans;
- ans.push(make_pair(pos, dp[pos]));
- for (int i=pos-1;i>=0;--i) {
- if (dp[i] != -1 && amount[i] + 1 == amount[pos]) {
- if (beds[i] + firs[dp[i]].E <= beds[pos] &&
- beds[i] <= beds[pos] - firs[dp[pos]].W) {
- ans.push(make_pair(i, dp[i]));
- pos = i;
- }
- }
- }
- while (!ans.empty()) {
- printf("%d %d\n", ans.top().first + 1, ans.top().second + 1);
- ans.pop();
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- output();
- return 0;
- }
Editing is locked.