Submission #958124

#	Time	Username	Problem	Language	Result	Execution time	Memory
958124		MinaRagy06	Split the sequence (APIO14_sequence)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

sequence

#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 100'005; const ll inf = 1e18; int a[N]; ll prf[N]; array<ll, 2> dp[205][N]; void solve(int j, int l, int r, int optl, int optr) { if (l > r || optl > optr) return; int i = (l + r) >> 1; for (int k = optl; k <= min(i - 1, optr); k++) { dp[j][i] = max(dp[j][i], {dp[j - 1][k][0] + prf[k] * (prf[i] - prf[k]), k}); } solve(j, l, i - 1, optl, min(optr, dp[j][i][1])); solve(j, i + 1, r, max(optl, dp[j][i][1]), optr); } int main() { ios_base::sync_with_stdio(0), cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; prf[i] = prf[i - 1] + a[i]; } m++; for (int i = 1; i <= n; i++) dp[0][i] = {-inf, -1}; for (int j = 1; j <= m; j++) { dp[j][0] = {-inf, -1}; solve(j, 1, n, 0, n - 1); } cout << dp[m][n][0] << '\n'; int j = m, i = n; vector<int> ans; while (j > 1) { ans.push_back(dp[j][i][1]); i = dp[j][i][1]; j--; } reverse(ans.begin(), ans.end()); for (auto x : ans) { cout << x << ' '; } cout << '\n'; return 0; }

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:16:48: error: no matching function for call to 'min(int&, std::array<long long int, 2>::value_type&)'
   16 |  solve(j, l, i - 1, optl, min(optr, dp[j][i][1]));
      |                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
sequence.cpp:16:48: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::array<long long int, 2>::value_type' {aka 'long long int'})
   16 |  solve(j, l, i - 1, optl, min(optr, dp[j][i][1]));
      |                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
sequence.cpp:16:48: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::array<long long int, 2>::value_type' {aka 'long long int'})
   16 |  solve(j, l, i - 1, optl, min(optr, dp[j][i][1]));
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
sequence.cpp:16:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   16 |  solve(j, l, i - 1, optl, min(optr, dp[j][i][1]));
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
sequence.cpp:16:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   16 |  solve(j, l, i - 1, optl, min(optr, dp[j][i][1]));
      |                                                ^
sequence.cpp:17:42: error: no matching function for call to 'max(int&, std::array<long long int, 2>::value_type&)'
   17 |  solve(j, i + 1, r, max(optl, dp[j][i][1]), optr);
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
sequence.cpp:17:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::array<long long int, 2>::value_type' {aka 'long long int'})
   17 |  solve(j, i + 1, r, max(optl, dp[j][i][1]), optr);
      |                                          ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
sequence.cpp:17:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::array<long long int, 2>::value_type' {aka 'long long int'})
   17 |  solve(j, i + 1, r, max(optl, dp[j][i][1]), optr);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
sequence.cpp:17:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   17 |  solve(j, i + 1, r, max(optl, dp[j][i][1]), optr);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
sequence.cpp:17:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   17 |  solve(j, i + 1, r, max(optl, dp[j][i][1]), optr);
      |                                          ^