Submission #1010645

#TimeUsernameProblemLanguageResultExecution timeMemory
1010645danikoynovTriple Jump (JOI19_jumps)C++14
5 / 100
1 ms612 KiB
#include<bits/stdc++.h> #define endl '\n' const int MAX_N = 110; int n, q, a[MAX_N]; void input() { std::cin >> n; for (int i = 1; i <= n; i ++) std::cin >> a[i]; } std::vector < std::pair < int, int > > fun; void precompute_pairs() { std::stack < int > st; for (int i = n; i > 0; i --) { while(!st.empty() && a[st.top()] <= a[i]) { fun.push_back({i, st.top()}); st.pop(); } st.push(i); } while(!st.empty()) st.pop(); for (int i = 1; i <= n; i ++) { while(!st.empty() && a[st.top()] <= a[i]) { ///std::cout << "pop " << st.top() << " from " << i << endl; fun.push_back({st.top(), i}); st.pop(); } st.push(i); } } int fp[MAX_N]; void single_query(int l, int r) { fp[r + 1] = 0; for (int i = r; i >= l; i --) { fp[i] = std::max(fp[i + 1], a[i]); } int res = 0; for (std::pair < int, int > cur : fun) { int id = 2 * cur.second - cur.first; if (id > r || cur.first < l) continue; //std::cout << "query " << cur.first << " " << cur.second << " " << id << endl; res = std::max(res, a[cur.first] + a[cur.second] + fp[id]); } /**for (int i = l; i <= r; i ++) for (int f = i + 1; f <= r; f ++) for (int j = 2 * f - i; j <= r; j ++) { if (a[i] + a[j] + a[f] == 174) std::cout << "winner " << i << " " << f << " " << j << endl; }*/ std::cout << res << endl; } void answer_queries() { std::cin >> q; for (int i = 1; i <= q; i ++) { int l, r; std::cin >> l >> r; single_query(l, r); } } void solve() { input(); precompute_pairs(); answer_queries(); } void speed() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); } int main() { speed(); solve(); return 0; } /* 15 12 96 100 61 54 66 37 34 58 21 21 1 13 50 81 1 6 14 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...