Submission #848151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848151	2023-09-11T12:49:12 Z	hehege	Feast (NOI19_feast)	C++14	Compilation error	0 ms	0 KB

feast

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e5 + 9;
const int N2 = 5e3 + 9;
const int INF = 1e18 + 9;

int n, k, a[N], ps[N], f[N], pre[N2], dp[N2][N2];

namespace sub1 {
	bool valid (){
		for (int i = 1; i <= n; i++) if (a[i] < 0) return 0;
		return 1;
	}
	
	void solve (){
		int res = 0;
		for (int i = 1; i <= n; i++) res += a[i];
		cout << res;
	}
}

namespace sub2 {
	bool valid (){
		int x = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) x++;
			if (x >= 2) break;
		}
		return x <= 1;
	}
	
	void solve (){
		int sum1 = 0, sum2 = 0, sumall = 0;
		bool flag = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) flag = 1;
			else if (flag == 0) sum1 += a[i];
			else sum2 += a[i];
		}
		for (int i = 1; i <= n; i++) sumall += a[i];
		if (k == 1) cout << max (sum1, max (sum2, sumall));
		else cout << sum1 + sum2;
	}
}

namespace sub3 {
	bool valid (){
		return k == 1;
	}
	
	void solve (){
		for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
		f[n] = ps[n];
		for (int i = n - 1; i >= 1; i--) f[i] = max (f[i + 1], ps[i]);
		int res = 0;
		for (int i = 1; i <= n; i++) res = max (res, f[i] - ps[i - 1]);
		cout << res;
	}
}

namespace sub45 {
	bool valid (){
		return n <= 500;
	}
	
	void solve (){
		dp[1][1] = a[1];
    	pre[1] = 0;
    	int res = max (0, a[1]);
    	for (int i = 2; i <= n; i++){
    		for (int j = 1; j <= k; j++){
    			if (j > i) continue;
    			dp[i][j] = max (dp[i][j], dp[i - 1][j] + a[i]);
    			for (int k = 1; k < i; k++) dp[i][j] = max (dp[i][j], dp[k][j - 1] + a[i]);
    			res = max (res, dp[i][j]);
    		}
    	}
    	cout << res;
	}
}

void sub6 (){
	dp[1][1] = a[1];
    pre[1] = max (0, a[1]);
    int res = max (0, a[1]);
    for (int i = 2; i <= n; i++){
    	for (int j = 1; j <= k; j++){
    		if (j > i) continue;
    		dp[i][j] = max (dp[i][j], max (dp[i - 1][j] + a[i], pre[j - 1] + a[i]));
    		pre[j] = max (pre[j], dp[i][j]);
    		res = max (res, dp[i][j]);
    	}
    }
    cout << res;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (sub1::valid ()) sub1::solve ();
    else if (sub2::valid ()) sub2::solve ();
    else if (sub3::valid ()) sub3::solve ();
    else if (sub45::valid ()) sub45::solve ();
    else sub6 ();
}

Compilation message

feast.cpp: In function 'void sub45::solve()':
feast.cpp:72:28: error: no matching function for call to 'max(int, long long int&)'
   72 |      int res = max (0, a[1]);
      |                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:72:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   72 |      int res = max (0, a[1]);
      |                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:72:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   72 |      int res = max (0, a[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 feast.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:
feast.cpp:72:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   72 |      int res = max (0, a[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 feast.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:
feast.cpp:72:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   72 |      int res = max (0, a[1]);
      |                            ^
feast.cpp: In function 'void sub6()':
feast.cpp:87:26: error: no matching function for call to 'max(int, long long int&)'
   87 |     pre[1] = max (0, a[1]);
      |                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:87:26: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   87 |     pre[1] = max (0, a[1]);
      |                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:87:26: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   87 |     pre[1] = max (0, a[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 feast.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:
feast.cpp:87:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   87 |     pre[1] = max (0, a[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 feast.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:
feast.cpp:87:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   87 |     pre[1] = max (0, a[1]);
      |                          ^
feast.cpp:88:27: error: no matching function for call to 'max(int, long long int&)'
   88 |     int res = max (0, a[1]);
      |                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:88:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   88 |     int res = max (0, a[1]);
      |                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from feast.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:
feast.cpp:88:27: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   88 |     int res = max (0, a[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 feast.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:
feast.cpp:88:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   88 |     int res = max (0, a[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 feast.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:
feast.cpp:88:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   88 |     int res = max (0, a[1]);
      |                           ^