fork download
copy 
  1. #include<cstdio>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define N 100010
  6. ll s[N];
  7. int ch[N];
  8. int houkou(int i, int j, int k){
  9.     ll cross = (j-i)*(s[k]-s[j])-(k-j)*(s[j]-s[i]);
  10.     return (cross>0)-(cross<0);
  11. }
  12.  
  13. int main(){
  14.     int T;
  15.     scanf("%d", &T);
  16.     while(T--){
  17.         int n, k;
  18.         scanf("%d%d ", &n, &k);
  19.         s[0] = 0;
  20.         for(int i=1; i<=n; i++){
  21.             s[i] = s[i-1] + (getchar()-48);
  22.         }
  23.         int l=0, r=k, len=1, op=1;
  24.         ch[1] = 0;
  25.         for(int i=k+1; i<=n; i++){
  26.             while(len>=2 && houkou(ch[len-1], ch[len], i-k)!=1){
  27.                 if(op == len) op--;
  28.                 len--;
  29.             }
  30.             ch[++len] = i-k;
  31.             while(op<len && houkou(ch[op], ch[op+1], i)!=-1) op++;
  32.             ll a=(s[i]-s[ch[op]])*(r-l), b=(s[r]-s[l])*(i-ch[op]);
  33.             if(a>b || (a==b && (i-ch[op] < r-l))){
  34.                 l = ch[op], r = i;
  35.             }
  36.         }
  37.         printf("%d %d\n", l+1, r);
  38.     }
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
2
17 5
00101011011011010
20 4
11100111100111110000
stdout
copy 
7 11
6 9
https://ideone.com/ifDKHH
language:
C++14 (gcc 8.3)
created:
6 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!