Submission #1225531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225531		denislav	Nile (IOI24_nile)	C++20	19 / 100	2096 ms	7568 KiB

nile

# include <iostream>
# include <vector>
# include <algorithm>
# include <cassert>
using namespace std;
# include "nile.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=1e5+11;

int n;
long long s;
pair<int,long long> a[MAX];

struct segtree
{
    long long tree[MAX*4];

    void build(int v=1, int l=1, int r=n)
    {
        if(l==r)
        {
            tree[v]=0;
            return ;
        }

        int mid=(l+r)/2;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    void update(int pos, long long d, int v=1, int l=1, int r=n)
    {
        if(l==r)
        {
            tree[v]=max(tree[v],d);
            return ;
        }

        int mid=(l+r)/2;
        if(pos<=mid) update(pos,d,v*2,l,mid);
        else update(pos,d,v*2+1,mid+1,r);
        tree[v]=max(tree[v*2],tree[v*2+1]);
    }

    long long query(int le, int ri, int v=1, int l=1, int r=n)
    {
        if(ri<l or r<le) return 0;
        if(le<=l and r<=ri) return tree[v];

        int mid=(l+r)/2;
        return max(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
    }
}tree;

int lm[MAX];
long long dp[MAX];

long long calc(long long d)
{
    int ptr=1;
    for(int i=1;i<=n;i++)
    {
        while(a[i].first-a[ptr].first>d) ptr++;
        lm[i]=ptr;
    }

    tree.build();
    for(int i=1;i<=n;i++) dp[i]=0;

    for(int i=1;i<=n;i++)
    {
        if(lm[i]!=i) dp[i]=max(dp[i],tree.query(lm[i],i-1)+a[i].second);
        dp[i]=max(dp[i],dp[i-1]);
        tree.update(i,dp[i-1]+a[i].second);
    }

    long long ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    return ans;
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    n=W.size();
    for(int i=0;i<n;i++)
    {
        a[i+1]={W[i],A[i]-B[i]};
        s+=A[i];
    }

    sort(a+1,a+n+1);
    vector<pair<long long,long long>> ans;
    long long from=1,res=calc(1);
    ans.push_back({from,res});
    while(from!=1e9+1)
    {
        long long l=from,r=1e9,mx=l;
        while(l<=r)
        {
            long long mid=(l+r)/2;
            long long resp=calc(mid);
            if(resp==res)
            {
                l=mid+1;
                mx=mid;
            }
            else r=mid-1;
        }

        if(mx==1e9) break;
        from=mx+1;
        res=calc(from);
        ans.push_back({from,res});
        if((int)ans.size()>n) assert(0);
    }

    //for(auto pa: ans) cout<<pa.first<<" "<<pa.second<<"\n";


    vector<long long> Final;
    Final.resize(E.size());
    for(int i=0;i<(int)E.size();i++)
    {
        int id=upper_bound(ans.begin(),ans.end(),make_pair((long long)E[i],INF))-ans.begin()-1;
        Final[i]=s-ans[id].second;
    }

    return Final;
}

/**
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18