fork download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. #define int long long
  6.  
  7. using namespace std;
  8.  
  9. signed main() {
  10. int n, len;
  11. cin >> n >> len;
  12. vector<int> A(2 * n);
  13. for (int i = 0; i < n; i++) {
  14. cin >> A[i];
  15. A[n + i] = A[i];
  16. }
  17. n *= 2;
  18.  
  19. vector<int> B = {0}, C = {0};
  20. for (int i = 0; i < n; i++)
  21. B.push_back(B.back() + A[i]);
  22. for (int i = 0; i < n; i++)
  23. C.push_back(C.back() + (A[i] * (A[i] + 1)) / 2);
  24. int ans = 0;
  25. for (int i = 0; i < n; i++) {
  26. if (B[i + 1] >= len) {
  27. int z = upper_bound(B.begin(), B.end(), B[i + 1] - len) - B.begin();
  28. int cnt = C[i + 1] - C[z];
  29. int days = B[i + 1] - B[z];
  30. int too = len - days;
  31. cnt += ((A[z - 1] * (A[z - 1] + 1)) / 2);
  32. cnt -= (((A[z - 1] - too) * (A[z - 1] - too + 1)) / 2);
  33. ans = max(ans, cnt);
  34. }
  35. }
  36. cout << ans;
  37. }
Success #stdin #stdout 0s 4232KB
stdin
3 4
1 3 2
stdout
8