The Best Vacation

思路

前缀和加贪心

贪心：我们的结尾点一定是在某一个月的最后一天。

贪心部分证明：我们选定两组数

A = a n − 2 , a n − 1 , a n , b 1 , b 2 , b 3 … … b n − 2 , b n − 1 A = a_{n - 2}, a_{n - 1}, a_{n}, b_{1}, b_{2}, b_{3}……b_{n - 2}, b_{n - 1} A=an−2​,an−1​,an​,b1​,b2​,b3​……bn−2​,bn−1​

B = a n − 1 , a n , b 1 , b 2 , b 3 … … b n − 2 , b n − 1 , b n B = a_{n - 1}, a_{n}, b_{1}, b_{2}, b_{3}……b_{n - 2}, b_{n - 1}, b_{n} B=an−1​,an​,b1​,b2​,b3​……bn−2​,bn−1​,bn​

假如我们的贪心策略是正确的，只需要证明 b n > a n − 2 b_{n} > a_{n - 2} bn​>an−2​即可，但是我们总能如愿吗，看一组样例。

2 4
5 2

1 2 3 4 5 1 2

chose 3 4 5 1
chose 4 5 1 2

显然这里贪心策略错了
ans 2 3 4 5

但是我们能看到的是这组样例的却也是以某一个月的最后一天结尾。

我们列出 a , b a, b a,b两个月的每天来。

a 1 , a 2 , a 3 , … … , a n − 2 , a n − 1 , a n a_{1}, a_{2}, a_{3}, ……, a_{n - 2}, a_{n - 1}, a_{n} a1​,a2​,a3​,……,an−2​,an−1​,an​

b 1 , b 2 , b 3 , … … , b n − 2 , b n − 1 , b n b_{1}, b_{2}, b_{3}, ……, b_{n - 2}, b_{n - 1}, b_{n} b1​,b2​,b3​,……,bn−2​,bn−1​,bn​

假如 b n > a n − 2 b_{n} > a_{n - 2} bn​>an−2​，我们选定的两组数是一定成立的。

或者 b n < a n − 2 b_{n} < a_{n - 2} bn​<an−2​，同样的我们可以得到 e a c h   i   f r o m   1   t o   n ， a n − i − 1 > b n − i + 1 each\ i\ from\ 1\ to\ n，a_{n - i - 1} > b_{n - i + 1} each i from 1 to n，an−i−1​>bn−i+1​

这里我们证明得到在上一步的贪心中，以月份 a a a结尾的是正确的，否则的话我们将得到以 b b b结尾的是正确的。

由此我们的贪心策略是正确的，所以我们只需要用前缀和来维护，然后通过枚举结尾点就行了。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 4e5 + 10;

ll a[N], s[N], x;
int n;

int main() {
    freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
    cin >> n >> x;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
        s[i] = s[i + n] = (1 + a[i]) * a[i] / 2;
    }
    for(int i = 1; i <= n << 1; i++)    a[i] += a[i - 1], s[i] += s[i - 1];
    ll ans = 0;
    for(int i = 1; i <= 2 * n; i++) {
        if(a[i] < x)    continue;
        ll low = a[i] - x;
        int p = lower_bound(a + 1, a + 1 + 2 * n, low) - a;
        if(a[i] - a[p] == x)    ans = max(ans, s[i] - s[p]);
        else {
            ll last = low - a[p - 1];
            ans = max(ans, s[i] - s[p - 1] - (1 + last) * last / 2);
        }
    }
    cout << ans << "\n";
	return 0;
}