Submission #1050097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050097		vjudge1	Art Exhibition (JOI18_art)	C++17	50 / 100	1075 ms	40308 KiB

art

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class SegmentTree {
public:
    SegmentTree(int size):size(size) {
        tree.resize(4*size,LLONG_MIN);
    }
    
    void build(const vector<long long>& data,int node,int start,int end) {
        if (start==end) {
            tree[node]=data[start];
        } else {
            int mid=(start+end)/2;
            build(data,2*node+1,start,mid);
            build(data,2*node+2,mid+1,end);
            tree[node]=max(tree[2*node+1],tree[2*node+2]);
        }
    }
    
    void update(int idx,long long value,int node,int start,int end) {
        if (start==end) {
            tree[node]=value;
        } else {
            int mid=(start+end)/2;
            if (start<=idx && idx<=mid) {
                update(idx,value,2*node+1,start,mid);
            } else {
                update(idx,value,2*node+2,mid+1,end);
            }
            tree[node]=max(tree[2*node+1],tree[2*node+2]);
        }
    }
    
    long long query(int l,int r,int node,int start,int end) {
        if (r<start || l>end) return LLONG_MIN;
        if (l<=start && end<=r) return tree[node];
        int mid=(start+end)/2;
        return max(query(l,r,2*node+1,start,mid),query(l,r,2*node+2,mid+1,end));
    }
    
private:
    vector<long long> tree;
    int size;
};

int main() {
    long long n;
    cin>>n;
    
    vector<pair<long long,long long>> art(n);
    vector<long long> values(n);
    
    for (long long i=0;i<n;++i) {
        cin>>art[i].first>>art[i].second;
        values[i]=art[i].second;
    }
    
    sort(art.begin(),art.end());
    
    SegmentTree segmentTree(n);
    segmentTree.build(values,0,0,n-1);
    
    long long ans=LLONG_MIN;
    
    for (int left=0;left<n;++left) {
        long long sum=0;
        long long min_size=art[left].first;
        
        for (int right=left;right<n;++right) {
            sum+=art[right].second;
            long long max_size=art[right].first;
            long long current_value=sum-(max_size-min_size);
            ans=max(ans,current_value);
        }
    }

    cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50