社区讨论
WA #6 求助/ll
CF1788E Sum Over Zero参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lqgk3ngn
- 此快照首次捕获于
- 2023/12/22 19:36 2 年前
- 此快照最后确认于
- 2023/12/22 21:42 2 年前
一眼了然后 RT。
甚至玄学的达到过WA #8,但是发现这种玄学没法同时通过6和8。
就这么个题已经整一下午了,救命()
CPP#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+84;
int n,bun,f[maxn];
long long bu[maxn],sum[maxn];
inline int lowbit(register int x){
return x&-x;
}
namespace Sherry_BiTre{
int T[maxn];
inline void Modify(int p,int val){
while(p<=bun+1){
T[p]=max(T[p],val);
p+=lowbit(p);
}
return ;
}
inline int Query(int p){
int res=-0x3f3f3f3f;
while(p){
res=max(res,T[p]);
p-=lowbit(p);
}
return res;
}
}
using namespace Sherry_BiTre;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
bu[i]=(sum[i]+=sum[i-1]);
}
sort(bu+1,bu+n+2);
bun=unique(bu+1,bu+n+2)-bu-1;
for(int i=1;i<=n;i++)
sum[i]=lower_bound(bu+1,bu+bun+1,sum[i])-bu;
memset(T,-0x3f,sizeof(T));
T[lower_bound(bu+1,bu+bun+1,0)-bu]=0;
for(int i=1;i<=n;i++)
Modify(sum[i],(f[i]=max(f[i-1],Query(sum[i])+i))-i);
printf("%d",f[n]);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...