제출 #466480

#제출 시각아이디문제언어결과실행 시간메모리
466480spike1236Art Exhibition (JOI18_art)C++14
50 / 100
108 ms17728 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define f first #define s second #define ll long long #define ld long double #define all(_v) _v.begin(), _v.end() #define sz(_v) (int)_v.size() #define pii pair <int, int> #define pll pair <ll, ll> #define veci vector <int> #define vecll vector <ll> const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; const double PI = 3.1415926535897932384626433832795; const double eps = 1e-9; const int MOD1 = 1e9 + 7; const int MOD2 = 998244353; const int MAXN = 2e5 + 10; int n; pll a[MAXN]; int ord[MAXN]; ll pref[MAXN]; ll t[MAXN << 2]; void upd(int pos, ll val, int v = 1, int tl = 1, int tr = n) { if(tl == tr) { t[v] = val; return; } int tm = tl + tr >> 1; if(pos <= tm) upd(pos, val, v << 1, tl, tm); else upd(pos, val, v << 1 | 1, tm + 1, tr); t[v] = min(t[v << 1], t[v << 1 | 1]); } ll get(int l, int r, int v = 1, int tl = 1, int tr = n) { if(l <= tl && tr <= r) return t[v]; if(l > tr || r < tl) return 1e18; int tm = tl + tr >> 1; return min(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr)); } void solve() { cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i].f >> a[i].s, upd(i, 1e18); sort(a + 1, a + n + 1); for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i].s; ll ans = a[1].s; upd(1, a[1].f); for(int i = 2; i <= n; ++i) { ans = max(ans, pref[i] - a[i].f - get(1, i - 1)); upd(i, pref[i - 1] + a[i].f); } if(n <= 5000) { for(int i = 1; i <= n; ++i) { for(int j = i; j <= n; ++j) { ans = max(ans, pref[j] - a[j].f - pref[i - 1] + a[i].f); } } } cout << ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int CNT_TESTS = 1; ///cin >> CNT_TESTS; for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) { solve(); if(NUMCASE != CNT_TESTS) cout << '\n'; } return 0; }

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

art.cpp: In function 'void upd(int, long long int, int, int, int)':
art.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
art.cpp: In function 'long long int get(int, int, int, int, int)':
art.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...