Submission #68474676

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define _f(i, l, r) for (int i = l; i <= r; ++i)
#define _r(i, r, l) for (int i = r; i >= l; --i)
#define FASTIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
const int N = 4.5e6+5, M = 1005, inf = 0xc0c0c0c0c0c0c0c0;
int n, s, a[N], f[N], pre[N];
int la[N];
struct SegmentTree {
    int dat[N<<2];
    void upd(int p, int l, int r, int x, int v) {
        if (l == r) return dat[p]=v, void();
        int mid = (l+r)>>1;
        x <= mid ? upd(p<<1, l, mid, x, v) : upd(p<<1|1, mid+1, r, x, v);
        dat[p] = min(dat[p<<1], dat[p<<1|1]);
    }
    int ask(int p, int l, int r, int L, int R) {
        if (L > R) return 0;
        if (L <= l && r <= R) return dat[p];
        int mid = (l+r)>>1;
        if (L > mid) return ask(p<<1|1, mid+1, r, L, R);
        if (mid >= R) return ask(p<<1, l, mid, L, R);
        return min(ask(p<<1, l, mid, L, R), ask(p<<1|1, mid+1, r, L, R));
    }
} sgt;
int B = 3;
signed main() {
	FASTIO;
    cin >> n >> s;
    _f(i, 1, n) cin >> a[i], a[i+(n<<1)]=a[i+n]=a[i];
    _f(i, 1, n*B) {
        pre[i] = la[a[i]];
        la[a[i]] = i;
    }
    _f(i, 1, n*B) {
        f[i] = a[i]+sgt.ask(1, 0, n*B, pre[i], i-1);
        sgt.upd(1, 0, n*B, i, f[i]);
    }
    int ans = 0;
    _f(i, 1, n) {
        if (f[n+i] > s) ans = max(ans, f[i] > s ? 0ll : i);
        else ans = max(ans, max(0ll, (s-f[n+i])/(f[(n<<1)+i]-f[n+i])+1)*n+i);
    }
    cout << ans;
	return 0;
}

Submission Info

Judge Result