Advertisement
Guest User

Untitled

a guest
Dec 8th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #define ILoveSonodaYu ios_base::sync_with_stdio(0);
  5. #define VeryMuch cin.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. const int N = 2e3+5, INF = 1e9;
  10.  
  11. long double L, W, d[2*N][N];
  12.  
  13. int n, m, a[N], b[N];
  14.  
  15. inline void read(){
  16.     cin >> L >> W;
  17.     cin >> n;
  18.     for(int i = 1; i <= n; ++i)
  19.         cin >> a[i];
  20.     cin >> m;
  21.     for(int i = 1; i <= m; ++i)
  22.         cin >> b[i];
  23. }
  24.  
  25. long double perimeter(int l1, int r1, int l2, int r2){
  26.     return (a[r1]-a[l1])+(b[r2]-b[l2])+hypotl(W,a[l1]-b[l2])+hypotl(W,a[r1]-b[r2]);
  27.     }
  28.  
  29. inline void ToLoveMyYu(){
  30.     for(int i = 2; i <= n+m; ++i)
  31.         for(int j = 1; j <= min(n,i-1); ++j)
  32.             d[i][j] = a[j]+b[i-j]-hypotl(a[j]-b[i-j],W);
  33.  
  34. }
  35.  
  36. struct Yu{
  37.     long double smile = -INF;
  38.     void give_yummy(long double x){
  39.         smile = max(smile,x);
  40.         }
  41.     long double Yusmile(){
  42.         return smile;
  43.     }
  44.     void bathe(){
  45.         smile = -INF;
  46.         }
  47. };
  48.  
  49. bool check(int S){
  50.     Yu best;
  51.     for(int r1 = 1; r1 <= n; ++r1){
  52.         best.bathe();
  53.         for(int r2 = 1; r2 <= m; ++r2){
  54.             int x = r1+r2-S;
  55.             if(x<0||x>r1+r2) continue;
  56.             if(x-r2>0 && x-r2<=n) best.give_yummy(d[x][x-r2]);
  57.             if(x-r2<=0) best.give_yummy(-hypotl(W,a[0]-b[0]));
  58.             if(best.Yusmile()!=-INF&&a[r1]+b[r2]+hypotl(W,a[r1]-b[r2])-best.Yusmile()<=L) return true;
  59.         }
  60.     }
  61.     return false;
  62. }
  63.  
  64. inline void solve(){
  65.     int l = 0, r = n+m, md;
  66.     while(r-l>1){
  67.         md = (l+r)/2;
  68.         if(check(md)) l = md;
  69.         else r = md;
  70.     }
  71.     cout << l;
  72. }
  73.  
  74.  
  75. int main(){
  76.     ILoveSonodaYu VeryMuch
  77.     read();
  78.     ToLoveMyYu();
  79.     solve();
  80.     check(5);
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement