QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122940 | #1808. Efficient Partitioning | JerryBlack | WA | 1ms | 5496kb | C++14 | 3.6kb | 2023-07-11 15:22:52 | 2023-07-11 15:22:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
const double eps=1e-12;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}
int P=998244353;
// int P=1e9+7;
namespace modint
{
int norm(int x){if(x<0)x+=P;if(x>=P)x-=P;return x;}
template<class T>
T power(T a,ll n){T ans=1;while(n){if(n&1)ans=ans*a;a=a*a;n>>=1;}return ans;}
struct Z
{
int x;
Z(int x=0):x(norm(x)){}
Z(ll x):x(norm(x%P)){}
int val() const{return x;}
Z operator-() const{return Z(norm(P-x));}
Z inv() const{assert(x!=0);return power(*this,P-2);}
Z&operator*=(const Z&rhs){x=(ll)x*rhs.x%P;return *this;}
Z&operator+=(const Z&rhs){x=norm(x+rhs.x);return *this;}
Z&operator-=(const Z&rhs){x=norm(x-rhs.x);return *this;}
Z&operator/=(const Z&rhs){return *this*=rhs.inv();}
friend Z operator*(const Z&lhs,const Z&rhs){Z res=lhs;res*=rhs;return res;}
friend Z operator+(const Z&lhs,const Z&rhs){Z res=lhs;res+=rhs;return res;}
friend Z operator-(const Z&lhs,const Z&rhs){Z res=lhs;res-=rhs;return res;}
friend Z operator/(const Z&lhs,const Z&rhs){Z res=lhs;res/=rhs;return res;}
friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
};
}
using namespace modint;
#define int ll
int cnt;
int root;
int dp[200005];
struct node
{
int a,b,ls,rs;
}tree[200005*300];
void update(int&p,int l,int r,int a,int b,int x)
{
if(!p)
{
p=++cnt;
tree[p].a=tree[p].b=-INF;
}
if(l==r)
{
tree[p].a=max(tree[p].a,a);
tree[p].b=max(tree[p].b,b);
}
else
{
int mid=(l+r)>>1;
if(x<=mid)update(tree[p].ls,l,mid,a,b,x);
else update(tree[p].rs,mid+1,r,a,b,x);
tree[p].a=max(tree[tree[p].ls].a,tree[tree[p].rs].a);
tree[p].b=max(tree[tree[p].ls].b,tree[tree[p].rs].b);
}
}
int query1(int p,int l,int r,int x,int y)
{
if(!p)return -INF;
if(x<=l&&r<=y)return tree[p].a;
else
{
int mid=(l+r)>>1;
int ans=-INF;
if(x<=mid)ans=max(ans,query1(tree[p].ls,l,mid,x,y));
if(mid<y)ans=max(ans,query1(tree[p].rs,mid+1,r,x,y));
return ans;
}
}
int query2(int p,int l,int r,int x,int y)
{
if(!p)return -INF;
if(x<=l&&r<=y)return tree[p].b;
else
{
int mid=(l+r)>>1;
int ans=-INF;
if(x<=mid)ans=max(ans,query2(tree[p].ls,l,mid,x,y));
if(mid<y)ans=max(ans,query2(tree[p].rs,mid+1,r,x,y));
return ans;
}
}
void solve()
{
tree[0].a=-INF;
tree[0].b=-INF;
int n;
cin>>n;
vector<int>a(n+1),b(n+1),c(n+1),pre(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
int zero=1e17;
int dif=0;
int l=0,r=2e17;
dp[0]=1e15;
for(int i=1;i<=n;i++)
{
dif+=a[i]+c[i]-c[i-1];
update(root,l,r,dp[i-1],b[i]+c[i-1]-pre[i-1],dp[i-1]-b[i]-c[i-1]+pre[i-1]+zero);
dp[i]=max(query2(root,l,r,zero+dif,r)+dif,query1(root,l,r,l,zero+dif));
}
cout<<dp[n];
}
/*
*/
#undef int
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
// cout<<fixed<<setprecision(15);
// int _;cin>>_;while(_--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5452kb
input:
2 1 -1 -1 4 1 -2
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5496kb
input:
1 1000000000 1000000000 1000000000
output:
3000000000
result:
ok answer is '3000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5468kb
input:
11 -323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840 -696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217 -465411342 -660775657 515997870 -34787742 628368976 84800619 -72...
output:
95993845
result:
wrong answer expected '91174984', found '95993845'