fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24.  
  25.  
  26.  
  27. vector<int> a;
  28.  
  29. //* Using Sorted set 
  30. //* O(nLogn)
  31.  
  32. int consistency1(int n, int x, int y) {
  33.     int ans = -LINF;
  34.  
  35.     vector<int> prefix(n+1, 0);
  36.     for(int i=1; i<=n; i++){
  37.         prefix[i] = prefix[i-1] + a[i-1];
  38.     }
  39.     for(int i=1; i<=y-x; i++){
  40.         prefix.push_back(-LINF);
  41.     }
  42.  
  43.     set<pair<int,int> > st;
  44.  
  45.     int size = prefix.size();
  46.  
  47.     int s = 0, e = 0;
  48.     int l = 0;
  49.  
  50.     while(e<size){
  51.         st.insert({prefix[e], e});
  52.  
  53.         while(e-l+1 > y-x+1){
  54.             st.erase({prefix[l], l});
  55.             l++;
  56.         }
  57.  
  58.         if(e-s+1 < y+1){
  59.             e++;
  60.         }
  61.         else{
  62.  
  63.             int maxi = (*st.rbegin()).first;
  64.  
  65.             ans = max(ans, maxi-prefix[s]);
  66.  
  67.             st.erase({prefix[l], l});
  68.  
  69.             l++;
  70.             s++;
  71.             e++;
  72.         }
  73.     }
  74.  
  75.  
  76.     return ans;
  77. }
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84. //* Using deque
  85. //* O(n)
  86.  
  87. int consistency2(int n, int x, int y) {
  88.     int ans = -LINF;
  89.  
  90.     vector<int> prefix(n+1, 0);
  91.     for(int i=1; i<=n; i++){
  92.         prefix[i] = prefix[i-1] + a[i-1];
  93.     }
  94.     for(int i=1; i<=y-x; i++){
  95.         prefix.push_back(-LINF);
  96.     }
  97.  
  98.     deque<int> down;
  99.  
  100.     int size = prefix.size();
  101.  
  102.     int s = 0, e = 0;
  103.     int l = 0;
  104.  
  105.     while(e<size){
  106.         while(!down.empty() && prefix[down.back()] < prefix[e] ) down.pop_back();
  107.         down.push_back(e);
  108.  
  109.         while(e-l+1 > y-x+1){
  110.             if(down.front() == l) down.pop_front();
  111.             l++;
  112.         }
  113.  
  114.         if(e-s+1 < y+1){
  115.             e++;
  116.         }
  117.         else{
  118.  
  119.             int maxi = prefix[down.front()];
  120.  
  121.             ans = max(ans, maxi-prefix[s]);
  122.  
  123.             if(down.front() == l) down.pop_front();
  124.  
  125.             l++;
  126.             s++;
  127.             e++;
  128.         }
  129.     }
  130.  
  131.  
  132.     return ans;
  133. }
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148. int practice(int n, int x, int y) {
  149.     int ans = 0;
  150.  
  151.  
  152.     return ans;
  153. }
  154.  
  155.  
  156.  
  157.  
  158. void solve() {
  159.  
  160.     int n, x, y;
  161.     cin>>n >> x >> y;
  162.  
  163. 	a.resize(n);
  164.     for(int i=0; i<n; i++) cin >> a[i];
  165.  
  166.     cout << consistency1(n, x, y) << " " << consistency2(n, x, y) << endl;
  167.  
  168.     // cout << consistency1(n, x, y) << " -> " << practice(n, x, y) << endl;
  169.  
  170.  
  171.  
  172.  
  173.  
  174. }
  175.  
  176.  
  177.  
  178.  
  179.  
  180. int32_t main() {
  181.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  182.  
  183.     int t = 1;
  184.     while (t--) {
  185.         solve();
  186.     }
  187.  
  188.     return 0;
  189. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10 5 6
-70 17 -37 -57 -20 73 76 54 17 54
stdout
copy 
274 274
https://ideone.com/Sj1lGi
language:
C++14 (gcc 8.3)
created:
20 hours 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!