fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l; i <= r; ++i)
  3. #define FOD(i,r,l) for(int i = r; i >= l; --i)
  4. #define task "CAVERN"
  5. #define int long long
  6. using namespace std;
  7. const int maxn = 5555;
  8. const int inf = 1e18;
  9. #define _58693_
  10. int n, m;
  11. int a[maxn], b[maxn];
  12. deque < int > qa, qb;
  13. int mxa[maxn], mxb[maxn];
  14. int ans = 0;
  15. int check(int d)
  16. {
  17.     //cerr << d << endl;
  18.     while(!qa.empty()) qa.pop_back();
  19.     while(!qb.empty()) qb.pop_back();
  20.     int res = inf;
  21.     FOD(i,m,0)
  22.     {
  23.         while(!qa.empty() && qa.front() > i + d) qa.pop_front();
  24.         while(!qa.empty() && a[qa.back()] < a[i]) qa.pop_back();
  25.         qa.push_back(i);
  26.         while(!qb.empty() && qb.front() > i + d) qb.pop_front();
  27.         while(!qb.empty() && b[qb.back()] < b[i]) qb.pop_back();
  28.         qb.push_back(i);
  29.         if(i <= m - d) mxb[i] = b[qb.front()];
  30.         if(i <= m - d) mxa[i] = a[qa.front()];
  31.         if(i <= m - d)
  32.         {
  33.             res = min(res, n - mxa[i] - mxb[i]);
  34.             if(res < 0) return 0;
  35.         }
  36.     }
  37.     return res;
  38.  
  39. }
  40. main()
  41. {
  42.     #ifdef _58693_
  43.     freopen(task".inp","r",stdin);
  44.     freopen(task".out","w",stdout);
  45.     #endif // _58693_
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(0);
  48.     cout.tie(0);
  49.     cin >> n >> m;
  50.     FOR(i,1,m) cin >> a[i];
  51.     FOR(i,1,m) cin >> b[i];
  52.     a[0] = 0;
  53.     b[0] = 0;
  54.     FOR(i,1,m)
  55.     {
  56.         //cout << i << " ";
  57.         ans = max(ans,i*check(i));
  58.     }
  59.     cout << ans;
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NH0qc0
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!