fork(6) download 
  1. #include <bits/stdc++.h>
  2. #define Fname "seq"
  3.  
  4. using namespace std;
  5.  
  6. const int MaxN = 3e5 + 7;
  7. const long long INF = 1e14;
  8.  
  9. long long h, a[MaxN], n, cur;
  10. unsigned long long d[MaxN], res = INF, k;
  11. bool sol;
  12. int main () {
  13. //  freopen (Fname".in", "r", stdin);
  14. //  freopen (Fname".out", "w", stdout);
  15.     scanf ("%d%d", &n, &h);
  16.     for (int i = 1; i <= n; ++ i)
  17.         a[i] = (i < h) ? 0 : i - h, d[i] = a[i] + d[i - 1];
  18. //      scanf ("%d", a + i), d[i] = a[i] + d[i - 1];
  19.     k = (h * (h + 1)) / 2;
  20.     for (int i = 1; i <= n - h + 1; ++ i)
  21.     {
  22.         if (a[i] <= 1 && k - (d[i + h - 1] - d[i - 1]) < res)
  23.         {
  24.             sol = true;
  25.             for (int j = i + 1; j < i + h; ++ j) {
  26.                 if (a[j] > j - (i + 1) + 2) {
  27.                     sol = false;
  28.                     i = j;
  29.                     break;
  30.                 }
  31.             }
  32.             if (sol)
  33.                 res = k - (d[i + h - 1] - d[i - 1]);
  34.         }
  35.     }
  36.     if (res == INF)
  37.         puts ("-1");
  38.     else
  39.         printf ("%I64d", res);
  40.     return 0;
  41. }
Time limit exceeded #stdin #stdout 5s 7416KB
comments (?)
stdin 
200000 100000
stdout 
Standard output is empty
https://ideone.com/N5NQJY
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!