1 solutions

  • 0
    @ 2025-11-5 18:04:04

    C++ :

    #include <algorithm>
    #include <cassert>
    #include <cstdio>
    #include <cstdlib>
    #include <deque>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <utility>
    #include <vector>
    using namespace std;
    
    #define FR(i,a,b) for(int i=(a);i<(b);++i)
    #define FOR(i,n) FR(i,0,n)
    #define FORALL(i,v) for(typeof((v).end())i=(v).begin();i!=(v).end();++i)
    #define CLR(x,a) memset(x,a,sizeof(x))
    #define BEND(v) (v).begin(),(v).end()
    #define MP make_pair
    #define PB push_back
    #define A first
    #define B second
    #define dump(x) cerr << #x << " = " << (x) << endl
    typedef long long ll; typedef long double ld;
    
    int W,vh,N;
    int xs[100000],ys[100000];
    int S;
    int ss[1000000];
    int main() {
      scanf("%d%d%d",&W,&vh,&N);
      assert(1 <= W && W <= 100000000);
      assert(1 <= vh && vh <= 1000000);
      assert(2 <= N && N <= 100000);
    
      FOR(i,N) {
        scanf("%d%d",&xs[i],&ys[i]);
        assert(1 <= xs[i] && xs[i] <= 100000000);
        assert(1 <= ys[i] && ys[i] <= 100000000);
      }
    
      FOR(i,N-1) assert(ys[i+1] > ys[i]);
    
      scanf("%d",&S);
      assert(1 <= S && S <= 1000000);
      FOR(i,S) {
        scanf("%d",&ss[i]);
        assert(1 <= ss[i] && ss[i] <= 1000000);
      }
      sort(&ss[0], &ss[S]);
    
      int lo = -1, hi = S;
      while (lo+1 < hi) {
        int mid = (lo+hi)/2;
    
        ll s = ss[mid];
    
        // 2*10^8 * 10^6 = 2*10^14
        ll l = 0, r = 200000000 * s;
        ll y = 0;
    
        bool ok = 1;
        FOR(i,N) {
          // 10^8 * 10^6 = 10^14
          l -= ll(ys[i]-y) * vh;
          r += ll(ys[i]-y) * vh;
    
          // 2*10^8 * 10^6 = 2*10^14
          if(l<xs[i]*s) l = xs[i]*s;
          if(r>(xs[i]+W)*s) r = (xs[i]+W)*s;
    
          if (r < l) {
    	ok = 0;
    	break;
          }
    
          y = ys[i];
        }
    
        if (ok) lo = mid;
        else hi = mid;
      }
    
      if (lo==-1) {
        printf("IMPOSSIBLE\n");
      } else {
        printf("%d\n", ss[lo]);
      }
    }
    
    
    • 1

    Information

    ID
    18751
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By