Submission #2423082
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int i = 0;i < (n);i++) #define FOR(i, a, b) for(int i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair<int32, int32>; using PLL = pair<int64, int64>; const double eps = 1e-6; template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;} template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;} const int64 mod = 1e9+7; /* int main(void){ int32 N; cin >> N; vector<int64> v(N); REP(i, N) cin >> v[i]; int64 maxi = 0; int64 res = 0; REP(i, N){ int64 cnt = (v[i]-1)/(maxi+1); if(cnt){ res += cnt; chmax(maxi, 1); } else maxi = v[i]; } cout << res << endl; } */ class RMQ{ private: int32 n; vector<int64> node, lazy; vector<bool> lazyFlag; public: RMQ(vector<int64> v){ int sz = v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, -INF_LL); lazy.resize(2*n-1, 0); lazyFlag.resize(2*n-1, false); for(int32 i = 0;i < sz;i++) node[i+n-1] = v[i]; for(int32 i = n-2;i >= 0;i--) node[i] = max(node[2*i+1], node[2*i+2]); } void eval(int32 k, int32 l, int32 r){ if(lazyFlag[k]){ node[k] = lazy[k]; if(r-l > 1){ lazy[2*k+1] = lazy[k]; lazy[2*k+2] = lazy[k]; lazyFlag[2*k+1] = lazyFlag[2*k+2] = true; } lazy[k] = 0; lazyFlag[k] = false; } } void update(int32 k, int64 x){ k += n-1; if(node[k] > x) return; node[k] = x; while(k){ k = (k-1)/2; node[k] = max(node[k*2+1], node[k*2+2]); } } int64 query(int32 a, int32 b, int32 k=0, int32 l=0, int32 r=-1){ if(r < 0) r = n; // eval(k, l, r); if(b <= l || r <= a) return -INF_LL; if(a <= l && r <= b) return node[k]; return max(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r)); } }; int main(void){ int32 M, N, K; cin >> N >> M >> K; vector<int64> A(N); vector<RMQ> rmq(K+1, RMQ(vector<int64>(N+1, 0))); REP(i, N) cin >> A[i]; REP(i, N){ REP(j, K){ rmq[j+1].update(i+1, rmq[j].query(max(0, i-M+1), i+1)+A[i]*(j+1)); } } cout << rmq[K].query(0, N+1) << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | maze1230 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2370 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:103:50: error: no matching function for call to ‘max(int, int32)’ rmq[j+1].update(i+1, rmq[j].query(max(0, i-M+1), i+1)+A[i]*(j+1)); ^ In file included from /usr/include/c++/5/bits/char_traits.h:39:0, from /usr/include/c++/5/ios:40, from /usr/include/c++/5/istream:38, from /usr/include/c++/5/sstream:38, from /usr/include/c++/5/complex:45, from /usr/include/c++/5/ccomplex:38, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52, from ./Main.cpp:1: /usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&) max(const _Tp& __a, const _Tp& __b) ^ /usr/include/c++/5/bits/stl_algobase.h:219:5: note: template argument deduction/substitution failed: ./Main.cpp:103:50: note: deduced conflicting types for ...