Submission #492579

#	Time	Username	Problem	Language	Result	Execution time	Memory
492579		Deepesson	Feast (NOI19_feast)	C++17	59 / 100	73 ms	2720 KiB

feast

#include <bits/stdc++.h>
#define MAX 505000
int N,K;
long long array[MAX];
typedef std::pair<long long,long long> pll;
pll func(long long C){
    long long a=1,b=0;
    long long max=0,maxval=0;
    long long pega=-C,npega=0;
    for(int i=0;i!=N;++i){
        pega+=array[i];
        if(pega>npega){
            npega=pega;
            b=a;
        }
        if(npega-C>=pega){
            pega=npega-C;
            a=b;
            ++a;
        }
        if(pega>max){
            max=pega;
            maxval=a;
        }
    }
    return {max,maxval};
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>K;
    for(int i=0;i!=N;++i)std::cin>>array[i];
    long long l=0,r=1LL<<50LL;
    while(l<r){
        long long m = (l+r)/2;
        long long res = func(m).second;
        if(res<=K){
            r=m;
        }else l=m+1;
    }
    auto res = func(l);
    if(!l){
        std::cout<<res.first<<"\n";
        return 0;
    }
    auto res2=func(l-1);
    long long dif = res2.second-res.second;
    long long bonus = std::min(K-res.second,dif)*l;
    if(std::min(K-res.second,dif)+res.second<K){
        assert(0);
    }
    std::cout<<(res.first+(res.second*l)+bonus)<<"\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29