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

Paste will expire never.

  1. // Меньшиков. Тренировка 12.
  2. // 12E. Водопровод [wpipe]
  3. // Рекурсивный перебор с отсечением
  4. // ibelyaev: 05Jan2011
  5.  
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. const int MAX_VALUE = 1e9;
  12. int k;
  13. vector<int> C,L;
  14. int x0, y0, x1, y1;
  15. int dx, dy;
  16. void input()
  17. {
  18.     cin>>x0>>y0>>x1>>y1>>k;
  19.     C.resize(k);
  20.     L.resize(k);
  21.     for (int i=0;i<k;i++)
  22.         cin>>L[i];
  23.     for (int j=0;j<k;j++)
  24.         cin>>C[j];
  25. }
  26. int _abs(int a)
  27. {
  28.     return (a<0) ? -a:a;
  29. }
  30. int minAmount = MAX_VALUE;
  31. int curAmount;
  32. bool isLast = false;
  33. void rec(int pos, int curLen, int totalLen)
  34. {
  35.     if ((totalLen - curLen) % L[pos] == 0)
  36.     {
  37.         int lastAmount = _abs(totalLen - curLen) / L[pos];
  38.         if (lastAmount <= C[pos])
  39.         {
  40.             if (isLast)
  41.                 minAmount = min(minAmount, curAmount + lastAmount);
  42.             else
  43.             {
  44.                 isLast = true;
  45.                 curAmount += lastAmount;
  46.                 C[pos] -= lastAmount;
  47.  
  48.                 rec(0,0,dy);
  49.  
  50.                 C[pos] += lastAmount;
  51.                 curAmount -= lastAmount;
  52.                 isLast = false;
  53.             }
  54.         }
  55.     }
  56.     if (pos == k-1)
  57.         return;
  58.     for (int x = -C[pos]; x <= C[pos]; x++)
  59.     {
  60.         C[pos]-= _abs(x);
  61.         curAmount += _abs(x);
  62.  
  63.         rec(pos+1, curLen + x * L[pos], totalLen);
  64.  
  65.         curAmount -= _abs(x);
  66.         C[pos] += _abs(x);
  67.     }
  68. }
  69.  
  70. void solve()
  71. {
  72.     dx = _abs(x0 - x1);
  73.     dy = _abs(y0 - y1);
  74.     // a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx
  75.     rec(0,0,dx);
  76.     if (minAmount == MAX_VALUE)
  77.         cout<<-1;
  78.     else
  79.         cout<<minAmount;
  80. }
  81. int main()
  82. {
  83.     freopen("input.txt","r",stdin);
  84.     freopen("output.txt","w",stdout);
  85.  
  86.     input();
  87.     solve();
  88.     return 0;
  89. }


Editing is locked.