제출 #206162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206162		SoGood	Art Exhibition (JOI18_art)	C++17	100 / 100	960 ms	33144 KiB

art

#include <bits/stdc++.h>
#define F first
#define S second
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)

using namespace std;


#define int ll

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;



const int N = 5e5 + 11;
const ll INF2 = 2e18 + 11;

template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

int n,t[N*4],pref[N];
pii a[N];
void upd(int v, int l, int r, int pos, int val) {
  if (l == r) {
    t[v]=val;
    return;
  }
  int md=l+((r - l) >> 1ll);
  if (pos <= md) upd(v+v,l,md,pos,val);
  else upd(v+v+1,md+1,r,pos,val);
  t[v]=max(t[v+v],t[v+v+1]);
}
int get(int v, int l, int r, int left, int right) {
  if (left > r || right < l) return 0;
  if (left <= l and r <= right) return t[v];
  int md=l+((r-l)>>1ll);
  return max(get(v+v,l,md,left,right),get(v+v+1,md+1,r,left,right));
}
main() {
  cin>>n;
  fo(i,1,n,1) cin>>a[i].F>>a[i].S;
  sort(a+1,a+n+1, greater<pii>());
  fo(i,1,n,1) pref[i]=pref[i-1]+a[i].S;
  foo(i,n,2,1) upd(1,1,n,i,pref[i]+a[i].F);
  int ans=-INF2;
  fo(l,1,n,1) chmax(ans,get(1,1,n,l,n)-pref[l-1]-a[l].F);
  cout<<ans;
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

art.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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