VPARTSUM - Tổng bộ phận

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stdio.h>
#include<set>
#define MAX   100100
using namespace std;
typedef set<int> si;
si st;
int a[MAX];
int s[MAX];
int n,k,p;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    scanf("%d",&p);
    int i;
    s[0]=0;
    for (i=1;i<=n;i=i+1) {
        scanf("%d",&a[i]);
        s[i]=(s[i-1]+a[i])%p;
    }
    k=k%p;
}
void process(void) {
    int b=p;
    int i,t;
    si::iterator it;
    for (i=n-1;i>=1;i=i-1) {
        if (st.find(s[i+1])==st.end()) st.insert(s[i+1]);
        it=st.end();
        it--;
        if (*it>=s[i]+k) {
            t=*(st.lower_bound(s[i]+k));
            if (t-s[i]<b) b=t-s[i];
        }
        if (*it>=s[i]+k-p) {
            t=*(st.lower_bound(s[i]+k-p));
            if (t-s[i]+p<b) b=t-s[i]+p;
        }
    }
    printf("%d",b);
}
int main(void) {
    init();
    process();
    return 0;
}

Download