제출 #467325

#제출 시각아이디문제언어결과실행 시간메모리
467325ivan_tudor휴가 (IOI14_holiday)C++14
100 / 100
3402 ms6396 KiB
#include "holiday.h" #include <vector> #include <iostream> #include <set> #include <algorithm> using namespace std; const int maxN = 100000; int N; int S; int D; vector<long long> A; long long res = 0; long long high_sum = 0; multiset<long long> high_values; multiset<long long> low_values; int L; int R; int can_visit; void insert_value(long long V) { high_values.insert(V); high_sum += V; while((int)(high_values.size()) > max(can_visit, 0)) { low_values.insert(*high_values.begin()); high_sum -= *high_values.begin(); high_values.erase(high_values.begin()); } } void erase_value(long long V) { if(low_values.find(V) != low_values.end()) { low_values.erase(low_values.find(V)); } else { high_values.erase(high_values.find(V)); high_sum -= V; } while((int)(high_values.size()) + 1 <= can_visit && (int)((int)(low_values.size())) >= 1) { high_values.insert(*low_values.rbegin()); high_sum += *low_values.rbegin(); low_values.erase(low_values.find(*low_values.rbegin())); } } void expand_right() { can_visit--; R++; insert_value(A[R]); } void contract_right() { can_visit++; erase_value(A[R]); R--; } void expand_left() { can_visit -= 2; L--; insert_value(A[L]); } void contract_left() { can_visit += 2; erase_value(A[L]); L++; } void solve(int l1, int l2, int r1, int r2) { // cerr << "solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n'; int l = (l1+l2)/2; while(L-1 >= l) expand_left(); while(R+1 <= max(r1, l)) expand_right(); while(L+1 <= l) contract_left(); while(R-1 >= max(r1, l)) contract_right(); long long score = high_sum; int best_r = R; while(R+1 <= r2) { expand_right(); if(high_sum > score) { score = high_sum; best_r = R; } // cerr << L << ' ' << R << ' ' << score << '\n'; // cerr << can_visit << '\n'; // for(int a: high_values) cerr << a << ' '; // cerr << '\n'; // cerr << high_sum << '\n'; // cerr << "\n\n"; } res = max(res, score); // cerr << "best_r = " << best_r << '\n'; if(l1 <= l-1) solve(l1, l-1, r1, best_r); if(l+1 <= l2) solve(l+1, l2, best_r, r2); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { N = n; S = start; D = d; A = vector<long long>(N); for(int i = 0; i < N; i++) A[i] = attraction[i]; // cerr << "D = " << D << '\n'; if(D == 0) return 0; //part 1: first left, then right high_values.insert(A[S]); high_sum = A[S]; L = R = S; can_visit = d; // cerr << "left, then right\n"; // cerr << "S = " << S << '\n'; solve(0, S, 0, N-1); reverse(A.begin(), A.end()); S = N-1 - S; high_values.clear(); low_values.clear(); // cerr << "new S = " << S << '\n'; high_values.insert(A[S]); high_sum = A[S]; L = R = S; can_visit = d; // cerr << "right, then left\n"; solve(0, S, 0, N-1); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...