TAChi-T009: Maximum Subarray Sum

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e5 + 5;

set<lli> pmx;
lli qs[N];

int main(){

    int n;
    lli md;
    scanf("%d%lld", &n, &md);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &qs[i]);
        qs[i] = (qs[i] + qs[i - 1]) % md;
    }
    lli mx = 0;
    pmx.insert(0);
    for(int i = 1; i <= n; ++i){
        lli x = qs[i];
        set<lli>::iterator itr = pmx.lower_bound(qs[i] + 1);
        if(itr != pmx.end()){
            x = (md + qs[i] - *itr) % md;
        }
        mx = max(mx, x);
        pmx.insert(qs[i]);
    }
    cout << mx;

    return 0;
}