fork 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.  
  30.  
  31.  
  32. //* Approach 1 : with deque O(n)
  33.  
  34.  
  35. //* Template 2
  36. //* 	We run fixed sliding window of size == y and size == x both at same time
  37.  
  38. int consistency1(int n, int x, int y) {
  39.     int ans = -LINF;
  40.  
  41.     deque<int> up;
  42.  
  43.     vector<int> prefix(n+1);
  44.     for(int i=0; i<n; i++)  prefix[i+1] = prefix[i] + a[i];
  45.     int sum = 0;
  46.  
  47.     //* Use 1 based indexing
  48.     for(int i=x; i<=n; i++){
  49.  
  50.         while(!up.empty() && prefix[i-x] < prefix[up.back()] ) up.pop_back();
  51.         up.push_back(i-x);
  52.  
  53.  
  54.         if(i-y-1>=0){
  55.             if( i-y-1 == up.front() ) up.pop_front();
  56.         }
  57.  
  58.         int mini = prefix[up.front()];
  59.  
  60.         ans = max(ans, prefix[i] - mini);
  61.  
  62.     }
  63.  
  64.     return ans;
  65. }
  66.  
  67.  
  68.  
  69.  
  70.  
  71. //* Approach 2 : with deque O(n)
  72.  
  73. //* Template 1 : 
  74.  
  75. int consistency2(int n, int x, int y) {
  76.     int ans = -LINF;
  77.  
  78.     vector<int> prefix(n+1, 0);
  79.     for(int i=1; i<=n; i++){
  80.         prefix[i] = prefix[i-1] + a[i-1];
  81.     }
  82.     for(int i=1; i<=y-x; i++){
  83.         prefix.push_back(-LINF);
  84.     }
  85.  
  86.     deque<int> down;
  87.  
  88.     int size = prefix.size();
  89.  
  90.     int s = 0, e = 0;
  91.     int l = 0;
  92.  
  93.     while(e<size){
  94.         while(!down.empty() && prefix[down.back()] < prefix[e] ) down.pop_back();
  95.         down.push_back(e);
  96.  
  97.         while(e-l+1 > y-x+1){
  98.             if(down.front() == l) down.pop_front();
  99.             l++;
  100.         }
  101.  
  102.         if(e-s+1 < y+1){
  103.             e++;
  104.         }
  105.         else{
  106.  
  107.             int maxi = prefix[down.front()];
  108.  
  109.             ans = max(ans, maxi-prefix[s]);
  110.  
  111.             if(down.front() == l) down.pop_front();
  112.  
  113.             l++;
  114.             s++;
  115.             e++;
  116.         }
  117.     }
  118.  
  119.  
  120.     return ans;
  121. }
  122.  
  123.  
  124.  
  125.  
  126.  
  127. //* Approach 2 :  Using Sorted set  O(nLogn)
  128.  
  129. //* Template 1 : 
  130.  
  131. int consistency3(int n, int x, int y) {
  132.     int ans = -LINF;
  133.  
  134.     vector<int> prefix(n+1, 0);
  135.     for(int i=1; i<=n; i++){
  136.         prefix[i] = prefix[i-1] + a[i-1];
  137.     }
  138.     for(int i=1; i<=y-x; i++){
  139.         prefix.push_back(-LINF);
  140.     }
  141.  
  142.     set<pair<int,int> > st;
  143.  
  144.     int size = prefix.size();
  145.  
  146.     int s = 0, e = 0;
  147.     int l = 0;
  148.  
  149.     while(e<size){
  150.         st.insert({prefix[e], e});
  151.  
  152.         while(e-l+1 > y-x+1){
  153.             st.erase({prefix[l], l});
  154.             l++;
  155.         }
  156.  
  157.         if(e-s+1 < y+1){
  158.             e++;
  159.         }
  160.         else{
  161.  
  162.             int maxi = (*st.rbegin()).first;
  163.  
  164.             ans = max(ans, maxi-prefix[s]);
  165.  
  166.             st.erase({prefix[l], l});
  167.  
  168.             l++;
  169.             s++;
  170.             e++;
  171.         }
  172.     }
  173.  
  174.  
  175.     return ans;
  176. }
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201. int practice(int n, int x, int y) {
  202.  
  203.  
  204. }
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211. void solve() {
  212.  
  213.     int n, x, y;
  214.     cin>>n >> x >> y;
  215.  
  216. 	a.resize(n);
  217.     for(int i=0; i<n; i++) cin >> a[i];
  218.  
  219.     cout << consistency1(n, x, y) << " " << consistency2(n, x, y) << " " << consistency3(n, x, y) << endl;
  220.  
  221.     // cout << consistency1(n, x, y) << " -> " << practice(n, x, y) << endl;
  222.  
  223.  
  224.  
  225.  
  226.  
  227. }
  228.  
  229.  
  230.  
  231.  
  232.  
  233. int32_t main() {
  234.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  235.  
  236.     int t = 1;
  237.     while (t--) {
  238.         solve();
  239.     }
  240.  
  241.     return 0;
  242. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10 4 6
-7 8 -3 -5 -2 7 6 4 -5 10
stdout
copy 
22 22 22
https://ideone.com/7i543g
language:
C++14 (gcc 8.3)
created:
8 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!