QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122934#1808. Efficient PartitioningJerryBlackWA 1ms5484kbC++143.6kb2023-07-11 15:10:252023-07-11 15:10:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 15:10:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5484kb
  • [2023-07-11 15:10:25]
  • 提交

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*80];
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=1e18;
    int dif=0;
    int l=0,r=2e18;
    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: 3468kb

input:

2
1 -1
-1 4
1 -2

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5484kb

input:

1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok answer is '3000000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5464kb

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'