RikkawithRCPC

Rikka is going to hold a worldwide competition, RCPC (Rikka's collegiate programming contest).
Preparing for a contest is time-consuming: It will take Rikka n days. Meanwhile, there are so many questions in the official QQ group of RCPC, raised by contestants, coaches, and even melon eating people. Therefore, Rikka decides to ignore the QQ group on some of the n days.
However, always ignoring questions may make contestants angry. Before the start of Day 1, the angry value A of contestants is 0. At the beginning of the i-th day, the angry value will be increased by $a_i$ . Then:

If A is strictly larger than a threshold T, contestants will be extremely angry, and Rikka will receive 2A points of attack. Then, at the end of this day, A will be cleared to 0;

If A is no larger than T and Rikka chooses to ignore questions, nothing will happen on this day;

If A is no larger than T and Rikka decides to answer questions, meanwhile, if Rikka ignores all questions on previous K days, i.e. from Day i-K to Day i-1, contestants will feel the hardness of Rikka. Rikka will not receive any attack, and at the end of this day, A will be cleared to 0;
Otherwise, even though Rikka chooses to answer questions, contestants will still blame Rikka for answering questions so slowly, and Rikka will receive A points of attack. At the end of this day, A will be cleared to 0.

Your task is to help Rikka to decide which days to answer questions so that the total attacks she received is minimized.

#include<cstdio> #include<iostream> #define rep(i,s,t) for(int i=s;i<=t;++i) #define db double using namespace std; #define ll long long const int N=1e6+11; int n,k,T; int a[N],q[N]; ll f[N],s[N],ans; int main(){ int l,r; scanf("%d%d%d",&n,&k,&T); ++k; rep(i,1,n)scanf("%d",a+i),s[i]=s[i-1]+a[i]; l=r=0; rep(i,1,n){ f[i]=f[i-1]; if(i>=k){ while(l!=r&&f[q[r-1]]-s[q[r-1]]<f[i-k]-s[i-k])--r; q[r++]=i-k; } while(l!=r&&s[q[l]]+T<s[i])++l; if(l!=r)f[i]=max(f[i],f[q[l]]-s[q[l]]+s[i]); } ans=s[n]; rep(i,0,n) if(s[n]-s[i]<=T) ans=min(ans,s[i]-f[i]); cout<<ans<<endl; return 0; }

详情