比赛 防止颓废的小练习v0.3 评测结果 TTTTT
题目名称 数字游戏 最终得分 0
用户昵称 Hzoi_chairman 运行时间 5.006 s
代码语言 C++ 内存使用 1.08 MiB
提交时间 2016-10-19 14:46:11
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<deque>
  4. using namespace std;
  5. int read()
  6. {
  7. int x,f=1;
  8. char ch;
  9. while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
  10. x=ch-48;
  11. while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
  12. return x*f;
  13. }
  14. void write(int x)
  15. {
  16. int cnt=0;char ch[50];
  17. while(ch[++cnt]=x%10+48,x/=10);
  18. while(putchar(ch[cnt]),--cnt);
  19. putchar('\n');
  20. }
  21. int sum[201000];
  22. deque<int> q;
  23. void push(int x)
  24. {
  25. while(!q.empty()&&sum[x]>=sum[q.back()])q.pop_back();
  26. q.push_back(x);
  27. }
  28. int main()
  29. {
  30. freopen("ggame.in","r",stdin);
  31. freopen("ggame.out","w",stdout);
  32. int n=read(),l=read(),r=read(),ans=-0x7f7f7f7f;
  33. for(int x,i=1;i<=n;i++)x=read(),sum[i]=sum[i-1]+x;
  34. for(int i=1;i<=r;i++)
  35. {
  36. push(i);
  37. if(i>=l)ans=max(ans,sum[i]);
  38. }
  39. for(int i=2;i<=n-l+1;i++)
  40. {
  41. while(!q.empty()&&q.front()-i<l-1)q.pop_front();
  42. ans=max(ans,sum[q.front()]-sum[i-1]);
  43. if(i+r<=n)push(i+r);
  44. }
  45. write(ans);
  46. fclose(stdin);
  47. fclose(stdout);
  48. }