fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <queue>
  8. #include <set>
  9. #include <map>
  10. #include <stack>
  11. using namespace std;
  12.  
  13. #define For(i,n) for(int i=0; i<(n); i++)
  14. #define mp(a,b) make_pair((a),(b))
  15. typedef long long ll;
  16. typedef pair<int,int> pii;
  17.  
  18. int main() {
  19.     //read input
  20.     int n,k;
  21.     scanf("%d %d",&n,&k);
  22.     vector<int> A; A.resize(n);
  23.     For(i,n) scanf("%d",&A[i]);
  24.     //for each i find out sum of elements in interval [i, i+k-1]
  25.     vector<ll> I; I.resize(n,0);
  26.     ll suma=0;
  27.     For(i,k-1) suma+=A[i];
  28.     for(int i=k-1; i<n; i++) {
  29.         suma+=A[i];
  30.         I[i-k+1]=suma;
  31.         suma-=A[i-k+1];
  32.     }
  33.     //for each i compute position with maximum absurdity in interval [0, i]
  34.     vector<pair<ll,int> > P; P.resize(n,mp(-1,-1));
  35.     ll maxi=0;
  36.     int pos=-1;
  37.     for(int i=k-1; i<n; i++) {
  38.         if(maxi<I[i-k+1]) {
  39.             maxi=I[i-k+1];
  40.             pos=i-k+1;
  41.         }
  42.         P[i]=mp(maxi,pos);
  43.     }
  44.     //for each b compute best a with use of array P
  45.     int a=-1,b=-1;
  46.     maxi=0;
  47.     for(int i=k; i<n-k+1; i++) {
  48.         if(I[i]+P[i-1].first>maxi) {
  49.             maxi=I[i]+P[i-1].first;
  50.             a=P[i-1].second;
  51.             b=i;
  52.         }
  53.     }
  54.     printf("%d %d\n",a+1,b+1);
  55. return 0;
  56. }
Success #stdin #stdout 0s 2824KB
comments (?)
stdin
copy 
5 2
3 6 1 1 6
stdout
copy 
1 4
https://ideone.com/PPEbIt
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!