Submission #683601

#	Time	Username	Problem	Language	Result	Execution time	Memory
683601		TimDee	Art Exhibition (JOI18_art)	C++17	100 / 100	381 ms	57544 KiB

art

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")

#define forn(i,n) for(int i=0;i<n;++i)
#define pb(x) push_back(x)
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pi pair<int,int>
#define f first
#define s second
#define int long long

const int inf = 1e18;
const int mod = 1e9+7;//998244353;
using ll = long long;

struct sgt {
	struct node {
		int pref=0,suf=0,in=0,sum=0;
	};
    vector<node> t;
    int n, sz;
    node merge(node a, node b) {
    	node r;
    	r.pref = max(a.pref,a.sum+b.pref);
    	r.suf = max(b.suf,b.sum+a.suf);
    	r.sum = a.sum+b.sum;
    	r.in = max({a.in, b.in, a.suf+b.pref});
    	return r;
    }
    node zero;
    void build(int v, int l, int r) {
        if (r-l==1) return;
        int m=(l+r)>>1;
        build(2*v+1,l,m);
        build(2*v+2,m,r);
        t[v]=merge(t[2*v+1],t[2*v+2]);
    }
    sgt(vector<int>&a) {
        n=a.size();
        sz=1;
        while (sz<n) sz<<=1;
        t.assign(2*sz-1,zero);
        forn(i,n) {
        	t[sz-1+i].pref=max(a[i],0ll);
        	t[sz-1+i].suf=max(a[i],0ll);
        	t[sz-1+i].sum=a[i];
        	t[sz-1+i].in=max(a[i],0ll);
        }
        build(0,0,sz);
    }
    node query(int v, int l, int r, int lx, int rx) {
        if (r<=lx || l>=rx) return zero;
        if (lx<=l && r<=rx) return t[v];
        int m=(l+r)>>1;
       	auto L=query(2*v+1,l,m,lx,rx);
       	auto R=query(2*v+2,m,r,lx,rx);
        return merge(L,R);
    }
    int query(int l, int r) {
        auto ret = query(0,0,sz,l,r);
        return max({ret.sum,ret.in,ret.pref,ret.suf});
    }
    void build(int v, int l, int r, int i) {
    	if (r<=i || l>i) return;
    	if (r-l==1) return;
    	int m=(l+r)>>1;
    	build(2*v+1,l,m,i);
    	build(2*v+2,m,r,i);
    	t[v]=merge(t[2*v+1],t[2*v+2]);
    }
    void set(int i, int x) {
    	t[sz-1+i].pref=x;
    	t[sz-1+i].suf=x;
    	t[sz-1+i].sum=x;
    	t[sz-1+i].in=x;
    	build(0,0,sz,i);
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
		
	int n; cin>>n;
	vector<pi> a(n);
	forn(i,n) cin>>a[i].f>>a[i].s;
	sort(all(a));

	vector<int> b(n);
	b[0]=a[0].s;
	for (int i=1; i<n; ++i) {
		b[i]=a[i].s-(a[i].f-a[i-1].f);
	}

	sgt st(b);
	int ans=0;
	forn(i,n) {
		st.set(i,a[i].s);
		ans=max(ans,st.query(i,n));
	}
	cout<<ans;

}

int32_t main() { 
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
   	//cin>>t;
    while(t--) solve();
    return 0;
}

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