제출 #546236

#제출 시각아이디문제언어결과실행 시간메모리
546236LunaMemeArt Exhibition (JOI18_art)C++14
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; typedef vector<pair<int, int>> vii; typedef vector<int> vi; typedef long long ll; #define PB push_back #define MP make_pair #define FOR(i, x, y) for (int i = x; i < y ; i ++) struct p{ ll size, val; bool operator<(p rhs){ return size < rhs.size; } }; int main(){ int n; cin >> n; vector<p> v(n); FOR(i, 0, n){ ll a, b; cin >> a >> b; p obj; obj.size = a; obj.val = b; v[i] = obj; } sort(v.begin(), v.end()); //left to right ll best_r = 0; int indx = 0; ll best_sum = 0, curr_sum = 0; FOR(i, 0, n){ if (curr_sum + v[i].val >= v[i].size - best_r){ best_r = v[i].size; indx = i; //best_sum += (curr_sum + v[i].val); curr_sum = 0; } else{ curr_sum += v[i].val; } } //cout << best_r << ' ' << best_sum << '\n'; //right to left int best_l = indx; curr_sum = 0; best_sum = 0; for(int i = indx; i >= 0; i --){ if (curr_sum + v[i].val >= best_l - v[i].size){ best_l = v[i].size; indx = i; best_sum += curr_sum + v[i].val; curr_sum = 0; } else{ curr_sum += v[i].val; } } cout << best_sum - (best_r - best_l) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...