oj.uz

Submission #958124

# Submission time Handle Problem Language Result Execution time Memory
958124 2024-04-05T01:39:11 Z MinaRagy06 Split the sequence (APIO14_sequence) C++17
Compilation error
 0 ms 0 KB 
#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

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);
      |                                          ^