제출 #1198269

#제출 시각아이디문제언어결과실행 시간메모리
1198269tawwieArt Exhibition (JOI18_art)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll, ll>> v; ll sz(int idx){ return v[idx].first; } ll val(int idx){ return v[idx].second; } int main(){ cin.tie(NULL)->ios_base::sync_with_stdio(false); int n; cin >> n; for(int i=0; i<n; i++){ ll a, b; cin >> a >> b; v.push_back({a, b}); // sz, val } sort(v.begin(), v.end()); //for(auto [i, j] : v) cout << i << ' ' << j << '\n'; // deque is actually overkill for this task // a two pointer approach with sliding window is all it takes // my main intuition was correct, just the implementation was a bit wonky ll ans = 0, s = 0; int l = 0; //deque<pair<ll, int>> dq; dq.push_back({sz(0), l}); s += val(0); // {size, index} for(int r=0; r<n; r++){ s += val(r); while(l < r){ if(s - (sz(r) - sz(l)) < s - val(l) - (sz(r) - sz(l + 1))){ s -= val(l); l--; }else{ break; } } ans = max(ans, s - (sz(r) - sz(l))); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...