Advertisement
Guest User

Untitled

a guest
Aug 24th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream f ("castig.in");
  6. ofstream g ("castig.out");
  7.  
  8. int n , x;
  9. long long a[100005];
  10. unsigned short k;
  11.  
  12. struct chestie
  13. {
  14.     int st , dr;
  15. }maxim[100005];
  16.  
  17. int main()
  18. {
  19.     int i , l = 0 , t , st , dr;
  20.     long long maxi2 = 99999999999 , maxi = 0 , mini = 999999999;
  21.  
  22.     f >> n >> k;
  23.  
  24.     for(i = 1 ; i <= n ; i++)
  25.     {
  26.         f >> x;
  27.         a[i] = x + a[i - 1];
  28.     }
  29.  
  30.     for(i = 1 ; i <= n - k + 1 ; i++)
  31.     {
  32.         if(maxi < a[i + k - 1] - a[i - 1])
  33.         {
  34.             maxi = a[i + k - 1] - a[i - 1];
  35.             l = 1;
  36.             maxim[l].dr = i + k - 1;
  37.             maxim[l].st = i;
  38.         }
  39.         else if(maxi == a[i + k - 1] - a[i - 1])
  40.         {
  41.             maxim[++l].dr = i + k - 1;
  42.             maxim[l].st = i;
  43.         }
  44.     }
  45.  
  46.     if(l > 2)
  47.     {
  48.         g << maxi;
  49.         return 0;
  50.     }
  51.  
  52.     if(l == 2)
  53.     {
  54.         if(maxim[2].st - 1 - (maxim[1].dr + 1) + 1 < k)
  55.         {
  56.             for(i = maxim[1].st + 1 ; i <= maxim[1].dr ; i++)
  57.                 if(i + k - 1 <= n && i + k - 1 >= maxim[2].st && maxi2 > a[i + k - 1] - a[i - 1])
  58.                     dr = i + k - 1 , st = i , maxi2 = a[i + k - 1] - a[i - 1];
  59.  
  60.             for(i = 1 ; i <= st - k ; i++)
  61.                 maxi2 = max(maxi2 , a[i + k - 1] - a[i - 1]);
  62.  
  63.             for(i = dr + 1 ; i <= n - k + 1 ; i++)
  64.                 maxi2 = max(maxi2 , a[i + k - 1] - a[i - 1]);
  65.         }
  66.         else maxi2 = maxi;
  67.  
  68.         g << maxi2;
  69.  
  70.         return 0;
  71.     }
  72.  
  73.     maxi = 0;
  74.  
  75.     for(i = 1 ; i <= maxim[1].st - k ; i++)
  76.         maxi = max(maxi , a[i + k - 1] - a[i - 1]);
  77.  
  78.     for(i = maxim[1].dr + 1 ; i <= n - k + 1 ; i++)
  79.         maxi = max(maxi , a[i + k - 1] - a[i - 1]);
  80.  
  81.     g << maxi;
  82.  
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement