fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. #include<queue>
  5. #include<vector>
  6. #include<climits>
  7. #include<algorithm>
  8. using namespace std;
  9. typedef struct node
  10. {
  11.     int x;
  12.     int y;
  13. }node;
  14. node Absurd(int n,int k,int *a)
  15. {
  16.     node ob1;
  17.  /*   int *A=(int*) calloc(k,sizeof(int));
  18.     int *B=(int*) calloc(k,sizeof(int));
  19.     long long int sumA=0,sumB=0; */
  20.     int j;
  21.     long long int M1=-1,M2=-1;
  22.     vector<long long int> V;
  23.     long long int *sum=(long long int*) calloc(n,sizeof(int));
  24.     for(int i=0;i<n;i++)
  25.     {
  26.         if(i!=0)
  27.             sum[i]=sum[i-1]+a[i];
  28.         else sum[i]=a[i];
  29.     }
  30.     for(int i=0;i<=(n-k-k);i++)
  31.     {
  32.         if(M1<(sum[i+k-1]-sum[i]))
  33.         {
  34.             ob1.x=(i);
  35.             M1=(sum[i+k-1]-sum[i]);
  36.             j=(i+k);
  37.         }
  38.     }
  39.     for(int i=j;i<=(n-k);i++)
  40.     {
  41.         if(M2<(sum[i+k-1]-sum[i]))
  42.         {
  43.             ob1.y=(i);
  44.             M2=(sum[i+k-1]-sum[i]);
  45.         }
  46.     }
  47. /*    for(int i=0;i<k;i++)
  48.         {
  49.             A[i]=a[i];
  50.             sumA+=a[i];
  51.         }
  52.     for(int i=k;i<(k+k);i++)
  53.         {
  54.             B[i-k-1]=a[i];
  55.             sumB+=a[i];
  56.         }
  57.     for(int i=k,j=(i+1);i<(n-k) && j<n;i++,j++)
  58.     {
  59.         sumA+=(a[i]-A[i%k]);
  60.         A[i%k]=a[i];
  61.         if(M1<sumA)
  62.         {
  63.             ob1.x=(k-i);
  64.             M1=sumA;
  65.         }
  66.         sumB+=a[j]-B[(j%(k+1)];
  67.         B[j%(k+1)]=a[j];
  68.         if(M2<sumB)
  69.         {
  70.             ob1.y=(j);
  71.             M2=sumB;
  72.         }
  73.     }*/
  74.     return ob1;
  75. }
  76. int main()
  77. {
  78.     int n,k;
  79.     scanf("%d%d",&n,&k);
  80.     int *a=(int*) calloc(n,sizeof(int));
  81.     for(int i=0;i<n;i++)
  82.         scanf("%d",&a[i]);
  83.     node ans=Absurd(n,k,a);
  84.     cout<<ans.x+1<<" "<<ans.y+1;
  85.     return 0;
  86. }
Success #stdin #stdout 0s 3032KB
comments (?)
stdin
copy 
5 2
3 6 1 1 6
stdout
copy 
1 4
https://ideone.com/pgKga4
language:
C++ (gcc 8.3)
created:
12 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!