Submission #1107112

#TimeUsernameProblemLanguageResultExecution timeMemory
1107112xnqsTriple Jump (JOI19_jumps)C++17
0 / 100
79 ms2420 KiB
// TODO implement optimally #include <iostream> #include <fstream> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <cmath> int x, q; int arr[500005]; int range_max_query(int l, int r) { int ret = 0; for (int i = l; i <= r; i++) { ret = std::max(ret,arr[i]); } return ret; } struct PQComp { bool operator() (int a, int b) { return arr[a] < arr[b]; } }; // take the 2 maxes, let their positions be 1 and 2 // therefore we have the following cases // // 1: ---1##--2 // 2: --###1--2 // 3: -1-2-#### int query(int l, int r) { if (r-l+1<=20) { int ret = 0; for (int i = l; i <= r; i++) { for (int j = i+1; j <= r; j++) { for (int k = j+(j-i); k <= r; k++) { ret = std::max(ret, arr[i]+arr[j]+arr[k]); } } } return ret; } std::priority_queue<int, std::vector<int>, PQComp> pq; for (int i = l; i <= r; i++) { pq.emplace(i); } std::vector<int> pos; while (!pq.empty()&&pos.size()<20) { int k = pq.top(); pq.pop(); pos.emplace_back(k); } int ret = 0; for (auto m1 : pos) { for (auto m2 : pos) { if (m1==m2) { continue; } if (m1>m2) std::swap(m1,m2); // 1 for (int i = m1+1; std::abs(m1-i) <= std::abs(m2-i) && i <= r; i++) { //std::cout << m1 << " " << i << " " << m2 << " " << arr[m1]+arr[m2]+arr[i] << "\n"; if (ret<arr[m1]+arr[m2]+arr[i]) { ret = arr[m1]+arr[m2]+arr[i]; } } // 2 for (int i = m1-1; std::abs(m1-i) <= std::abs(m1-m2) && i >= l; i--) { //std::cout << i << " " << m1 << " " << m2 << " " << arr[m1]+arr[m2]+arr[i] << "\n"; if (ret<arr[m1]+arr[m2]+arr[i]) { ret = arr[m1]+arr[m2]+arr[i]; } } // 3 for (int i = m2+(m2-m1); i <= r; i++) { //std::cout << m1 << " " << m2 << " " << i << " " << arr[m1]+arr[m2]+arr[i] << "\n"; if (ret<arr[m1]+arr[m2]+arr[i]) { ret = arr[m1]+arr[m2]+arr[i]; } } } } return ret; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); std::cin >> x; for (int i = 1; i <= x; i++) { std::cin >> arr[i]; } std::cin >> q; while (q--) { int l, r; std::cin >> l >> r; std::cout << query(l,r) << "\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...