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. //* Template : 
  84.  
  85. //* Using deque
  86. //* O(n)
  87.  
  88. int consistency2(int n, int x, int y) {
  89.     int ans = -LINF;
  90.  
  91.     vector<int> prefix(n+1, 0);
  92.     for(int i=1; i<=n; i++){
  93.         prefix[i] = prefix[i-1] + a[i-1];
  94.     }
  95.     for(int i=1; i<=y-x; i++){
  96.         prefix.push_back(-LINF);
  97.     }
  98.  
  99.     deque<int> down;
  100.  
  101.     int size = prefix.size();
  102.  
  103.     int s = 0, e = 0;
  104.     int l = 0;
  105.  
  106.     while(e<size){
  107.         while(!down.empty() && prefix[down.back()] < prefix[e] ) down.pop_back();
  108.         down.push_back(e);
  109.  
  110.         while(e-l+1 > y-x+1){
  111.             if(down.front() == l) down.pop_front();
  112.             l++;
  113.         }
  114.  
  115.         if(e-s+1 < y+1){
  116.             e++;
  117.         }
  118.         else{
  119.  
  120.             int maxi = prefix[down.front()];
  121.  
  122.             ans = max(ans, maxi-prefix[s]);
  123.  
  124.             if(down.front() == l) down.pop_front();
  125.  
  126.             l++;
  127.             s++;
  128.             e++;
  129.         }
  130.     }
  131.  
  132.  
  133.     return ans;
  134. }
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141. //* Template 2
  142.  
  143. //* Using deque
  144. //* O(n)
  145.  
  146. int consistency3(int n, int x, int y) {
  147.     int ans = -LINF;
  148.  
  149.     deque<int> up;
  150.  
  151.     vector<int> prefix(n+1);
  152.     for(int i=0; i<n; i++)  prefix[i+1] = prefix[i] + a[i];
  153.     int sum = 0;
  154.  
  155.     //* Use 1 based indexing
  156.     for(int i=x; i<=n; i++){
  157.  
  158.         while(!up.empty() && prefix[i-x] < prefix[up.back()] ) up.pop_back();
  159.         up.push_back(i-x);
  160.  
  161.  
  162.         if(i-y-1>=0){
  163.             if( i-y-1 == up.front() ) up.pop_front();
  164.         }
  165.  
  166.         int mini = prefix[up.front()];
  167.  
  168.         ans = max(ans, prefix[i] - mini);
  169.  
  170.     }
  171.  
  172.     return ans;
  173. }
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191. int practice(int n, int x, int y) {
  192.  
  193.  
  194. }
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201. void solve() {
  202.  
  203.     int n, x, y;
  204.     cin>>n >> x >> y;
  205.  
  206. 	a.resize(n);
  207.     for(int i=0; i<n; i++) cin >> a[i];
  208.  
  209.     cout << consistency1(n, x, y) << " " << consistency2(n, x, y) << " " << consistency3(n, x, y) << endl;
  210.  
  211.     // cout << consistency1(n, x, y) << " -> " << practice(n, x, y) << endl;
  212.  
  213.  
  214.  
  215.  
  216.  
  217. }
  218.  
  219.  
  220.  
  221.  
  222.  
  223. int32_t main() {
  224.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  225.  
  226.     int t = 1;
  227.     while (t--) {
  228.         solve();
  229.     }
  230.  
  231.     return 0;
  232. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
10 4 6
-7 8 -3 -5 -2 7 6 4 -5 10
stdout
copy 
22 22 22
https://ideone.com/k2vUrn
language:
C++14 (gcc 8.3)
created:
1 day 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!