v 0. Pasted by slipstak2 as cpp at 2011-10-25 19:47:31 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Олимпиадные задачи
  3. // Задача B. Еловая алея
  4. // ibelyaev: 25Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. struct fir {
  25.     int W,E;
  26. };
  27. vector<fir> firs;
  28. vector<int> beds;
  29. int n,m;
  30. vector<int> dp,amount;
  31. void input(){
  32.     scanf("%d", &n);
  33.     firs.resize(n);
  34.     for (int i=0;i<n;++i)
  35.         scanf("%d %d", &firs[i].W, &firs[i].E);
  36.     scanf("%d", &m);
  37.     beds.resize(m);
  38.     for (int i=0;i<m;++i)
  39.         scanf("%d", &beds[i]);
  40.     dp.resize(m,-1);
  41.     amount.resize(m);
  42. }
  43. void solve(){
  44.     int minE = 0;
  45.     for (int i=0;i<firs.size();++i) {
  46.         if (firs[i].E < firs[minE].E)
  47.             minE = i;
  48.     }
  49.     dp[0] = minE;
  50.     amount[0] = 1;
  51.     for (int i=1;i<beds.size();++i) {
  52.         int bestF = -1;
  53.         int maxAmount = 0;
  54.         for (int j=i-1;j>=0;--j) {
  55.             if (dp[j] != -1 && beds[j] + firs[dp[j]].E <= beds[i]) {
  56.                 for (int k=0;k<firs.size();++k) {
  57.                     if (beds[j] <= beds[i] - firs[k].W) {
  58.                         if (amount[j] > maxAmount) {
  59.                             maxAmount = amount[j];
  60.                             bestF = k;
  61.                         }
  62.                         if (amount[j] == maxAmount && firs[k].E < firs[bestF].E) {
  63.                             bestF = k;
  64.                         }
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.         if (bestF == -1) {
  70.             dp[i] = minE;
  71.             amount[i] = 1;
  72.         }
  73.         else {
  74.             dp[i] = bestF;
  75.             amount[i] = maxAmount + 1;
  76.         }
  77.     }
  78. }
  79. void output() {
  80.     int pos = max_element(amount.begin(), amount.end()) - amount.begin();
  81.     printf("%d\n", amount[pos]);
  82.     stack<pair<int,int> > ans;
  83.     ans.push(make_pair(pos, dp[pos]));
  84.     for (int i=pos-1;i>=0;--i) {
  85.         if (dp[i] != -1 && amount[i] + 1 == amount[pos]) {
  86.             if (beds[i] + firs[dp[i]].E <= beds[pos] &&
  87.                 beds[i] <= beds[pos] - firs[dp[pos]].W) {
  88.                 ans.push(make_pair(i, dp[i]));
  89.                 pos = i;
  90.             }
  91.         }
  92.     }
  93.     while (!ans.empty()) {
  94.         printf("%d %d\n", ans.top().first + 1, ans.top().second + 1);
  95.         ans.pop();
  96.     }
  97. }
  98. int main()
  99. {
  100.     freopen("input.txt","r",stdin);
  101.     freopen("output.txt","w",stdout);
  102.  
  103.     input();
  104.     solve();
  105.     output();
  106.  
  107.     return 0;
  108. }


Editing is locked.