제출 #1225513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225513		denislav	나일강 (IOI24_nile)	C++20	67 / 100	2095 ms	9028 KiB

nile

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

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=0, 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(int 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<long long> Final;
    Final.resize(E.size());
    for(int i=0;i<(int)E.size();i++)
    {
        Final[i]=s-calc(E[i]);
    }

    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: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18