v 0. Pasted by slipstak2 as cpp at 2011-01-17 21:15:15 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 15.
  2. // 15E. Семечки [seeds]
  3. // ibelyaev: 17Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. int n;
  13. vector<int> Pr,B,posPr,PrRev;
  14. int maxP = -1, resL = -1, resP = -1;
  15. void input()
  16. {
  17.     cin>>n;
  18.     Pr.resize(n); B.resize(n);
  19.     for (int i=0;i<n;i++) {
  20.         cin>>Pr[i];
  21.         posPr.push_back(Pr[i]);
  22.         posPr.push_back(Pr[i]-1);
  23.     }
  24.     for (int i=0;i<n;i++)
  25.         cin>>B[i];
  26. }
  27. int calc(int L, int P, vector<int> &Pr) {
  28.     int curB = 0;
  29.     // идем слева
  30.     bool isLeft = true;
  31.     for (int i=0; i <= L;i++) {
  32.         if (Pr[i]<P)
  33.             isLeft = false;
  34.     }
  35.     if (isLeft) {
  36.         int ML = n-1;
  37.         for (int i=L+1;i<n-1;i++) {
  38.             if (Pr[i] <= P) {
  39.                 ML = i;
  40.                 break;
  41.             }
  42.         }
  43.         for (int i=L+1; i<=ML; i++)
  44.             curB += B[i];               
  45.     }
  46.     return curB;
  47. }
  48. void solve()
  49. {
  50.     sort(posPr.begin(),posPr.end());
  51.     vector<int>::iterator it = unique(posPr.begin(),posPr.end());
  52.     posPr.resize( it - posPr.begin());
  53.     PrRev = Pr;
  54.     reverse(PrRev.begin(),PrRev.end());
  55.     for (int L=0; L<=n-2; L++) {
  56.         for (vector<int>::iterator P = posPr.begin(); P != posPr.end(); P++) {
  57.             int f = calc(L, *P,Pr);
  58.  
  59.             int s = calc(n-2-L, *P,PrRev);
  60.  
  61.             int curB = f+s;
  62.  
  63.             int curP = curB * *P;
  64.             if (curP > maxP) {
  65.                 maxP = curP;
  66.                 resP = *P;
  67.                 resL = L;
  68.             }
  69.         }
  70.     }
  71.     cout<<resL+1<<' '<<resP;
  72. }
  73. int main()
  74. {
  75.     freopen("input.txt","r",stdin);
  76.     freopen("output.txt","w",stdout);
  77.  
  78.     input();
  79.     solve();
  80.     return 0;
  81. }


Editing is locked.