Submission

[PPPPPPPPPP]

Score: 100

User: fluke

Problemset: 02.Forbidden Boss Room

Language: cpp

Time: 0.036 second

Submitted On: 2025-04-06 09:02:40

#include <bits/stdc++.h>
#define ll long long
#define f first 
#define s second 
#define pii pair<int,int>
#define emb emplace_back
#define em emplace 
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define DB cout<<"\n";system("pause");
using namespace std;

void solve(){
    ll n,m;
    cin>>n>>m;
    vector <ll> arr(n+1) , qsum(n+1);
    for(int i=1;i<=n;i++)cin>>arr[i];

    ll ans = 0;
    set <ll> same;
    same.insert(0);

    for(int i=1;i<=n;i++){
        qsum[i] = (qsum[i-1] + arr[i])%m;

        ll want = qsum[i] + 1;
        if(want == m)want = 0;
        // want = *prev(same.upper_bound(want));
        auto it = same.lower_bound(want);

        if(it == same.end()){
            ans = max(ans , qsum[i]);
            same.insert(qsum[i]);
        }
        else {
            ll remain = qsum[i] - *it;
            if(remain < 0)remain += m;
            ans = max(ans,remain);
            same.insert(qsum[i]);
        }

    }

    cout<<ans << "\n";
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);
    int q;
    cin>>q;
    while(q--)solve();
}