#include <bits/stdc++.h>
#define N 500010
#define f first
#define int long long
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, q, v[N], C[5010][5010], menor[5010][5010], dp[5010][5010];
int ans, tree[4*N];
void build(int nod, int a, int b)
{
if(a == b)
{
tree[nod] = v[a];
return;
}
build(2*nod, a, (a+b)/2);
build(2*nod + 1, (a + b)/2 + 1, b);
tree[nod] = max(tree[2*nod], tree[2*nod + 1]);
}
int query(int nod, int a, int b, int i, int j)
{
if(j < a or i > b) return 0;
if(i <= a and j >= b) return tree[nod];
return max(query(2*nod, a, (a+b)/2, i, j), query(2*nod + 1, (a+b)/2 + 1, b, i, j));
}
int solve(int i, int j)
{
if(i > j) return 0;
if(dp[i][j] != -1) return dp[i][j];
return dp[i][j] = max({solve(i + 1, j), solve(i, j - 1), C[i][j]});
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++) cin>>v[i];
if(n <= 5000)
{
memset(dp, -1, sizeof dp);
for(int i = 1; i <= n; i++)
{
menor[i][i] = v[i];
for(int j = i + 1; j <= n; j++)
menor[i][j] = max(menor[i][j - 1], v[j]);
}
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
int mid = (i + j)/2;
C[i][j] = menor[i + 1][mid] + v[i] + v[j];
}
}
cin>>q;
for(int i = 1, l, r; i <= q; i++)
{
cin>>l>>r;
cout<<solve(l, r)<<"\n";
}
}
else
{
build(1, 1, n);
vector<pii> val;
for(int i = 1; i <= n; i++) val.push_back({v[i], i});
sort(val.rbegin(), val.rend());
for(int i = 0; i < min(50, (int)val.size()); i++)
{
int vi = val[i].f, p = val[i].s;
for(int x = 1; x <= n; x++)
{
int mid = (x + p)/2;
int l = min(x, p), r = max(x, p);
int opt = query(1, 1, n, l + 1, mid);
ans = max(ans, opt + v[l] + v[r]);
}
}
int a, b;
cin>>a>>b;
cout<<ans<<"\n";
}
}
Compilation message
jumps.cpp: In function 'int32_t main()':
jumps.cpp:97:45: error: no matching function for call to 'min(int, long long int)'
for(int i = 0; i < min(50, (int)val.size()); i++)
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from jumps.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
min(const _Tp& __a, const _Tp& __b)
^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: template argument deduction/substitution failed:
jumps.cpp:97:45: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
for(int i = 0; i < min(50, (int)val.size()); i++)
^
In file included from /usr/include/c++/7/bits/specfun.h:45:0,
from /usr/include/c++/7/cmath:1914,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
from jumps.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
min(const _Tp& __a, const _Tp& __b, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: template argument deduction/substitution failed:
jumps.cpp:97:45: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
for(int i = 0; i < min(50, (int)val.size()); i++)
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from jumps.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
min(initializer_list<_Tp> __l)
^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
jumps.cpp:97:45: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
for(int i = 0; i < min(50, (int)val.size()); i++)
^
In file included from /usr/include/c++/7/algorithm:62:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
from jumps.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
min(initializer_list<_Tp> __l, _Compare __comp)
^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
jumps.cpp:97:45: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
for(int i = 0; i < min(50, (int)val.size()); i++)
^
jumps.cpp:99:8: warning: unused variable 'vi' [-Wunused-variable]
int vi = val[i].f, p = val[i].s;
^~
