Submission #159272

#	Time	Username	Problem	Language	Result	Execution time	Memory
159272		socho	Art Exhibition (JOI18_art)	C++14	30 / 100	1083 ms	1016 KiB

art

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

struct node {

   long long s, e, m, val;
   node *l, *r;
   node (long long _s, long long _e) {
       s = _s;
       e = _e;
       m = (s + e)/2;
       val = 0;
       if (s == e) return;
       l = new node(s, m);
       r = new node(m+1, e);
   }

   void upd(long long p, long long v) {
       if (s == p && s== e) {
           val = v;
           return;
       }
       if (p <= m) {
           l->upd(p, v);
       }
       else {
           r->upd(p, v);
       }
       val = l->val + r->val;
   }

   long long qry(long long qs, long long qe) {
       if (qs <= s && e <= qe) {
           return val;
       }
       else if (qs > e || s > qe) {
           return 0;
       }
       else {
           return l->qry(qs, qe) + r->qry(qs, qe);
       }
   }
} *root;

void init(long long N) {
   root = new node(0, N-1);
}

void update(long long P, long long V) {
   root->upd(P, V);
}

long long query(long long A, long long B) {
   return root->qry(A, B);
}

int main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	long long n;
	cin >> n;
	vector<pair<long long, long long> > works;
	for (long long i=0; i<n; i++) {
		long long siz, val;
		cin >> siz >> val;
		works.push_back(make_pair(siz, val));
	}
	sort(works.begin(), works.end());
	init(n);
	for (long long i=0; i<n; i++) {
		update(i, works[i].second);
	}
	long long best = LLONG_MIN;
	for (long long i=0; i<n; i++) {
		for (long long j=i; j<n; j++) {
			best = max(best, query(i, j) + works[i].first - works[j].first);
		}
	}
	cout << best << endl;
	
}

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