Submission #1103146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103146	2024-10-20T09:24:23 Z	DuongKiet	Feast (NOI19_feast)	C++17	Compilation error	0 ms	0 KB

feast

#include <bits/stdc++.h>
#define N 300005
#define inf (long long) 1e17
#define ll long long
#define int long long
#define ii pair <int,long long>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back

using namespace std;

const unsigned ll Mod = 1000000007LL;

int n, k, a[N];
void init(){

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}
bool ifsub1(){

    for (int i = 1; i <= n; i++)
        if (a[i] < 0) return 0;
    return 1;
}
void sub1(){

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i];
    cout << ans << '\n';
}
int pos;
bool ifsub2(){

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] < 0) {pos = a[i]; cnt++;}
    return (cnt < 2);
}
void sub2(){

    int sum = 0, suml = 0, am = 0;
    bool kt = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < 0) {
            kt = 1;
            am = a[i];
        }
        if (!kt) suml += a[i];
        sum += a[i];
    }
    if (k > 1)
        cout << sum - am << '\n';
    else cout << max(suml, max(sum, sum - suml - am));
}
void sub3(){
    int ans = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(0ll, res + a[i]);
        ans = max(ans, res);
    }
    cout << ans << '\n';
}
//int pa[N], sz[N];
//int findpa(int u){
//
//    if (u == pa[u]) return u;
//    return pa[u] = findpa(pa[u]);
//}
//void Union(int a, int b){
//
//    a = findpa(a);
//    b = findpa(b);
//    if (a == b) return;
//    if (sz[a] < sz[b]) swap(a,b);
//    pa[b] = a;
//    sz[a] += sz[b];
//    sum[a] += sum[b];
//}
//vector <ii> d;
//void Add(int u){
//    d.pb({u, sum[u]});
//}
//void sub6(){
//    for (int i = 1; i <= n; i++){
//        pa[i] = i;
//        sz[i] = 1;
//        sum[i] = a[i];
//    }
//    int parduong, param;
//    bool task = 0;
//    if (a[1] >= 0) {parduong = 1; task = 1;}
//    else param = 1;
//    for (int i = 1; i <= n; i++){
//        if (a[i] >= 0) {
//            if (task)
//                Union(parduong, i);
//            else parduong = i;
//            task = 1;
//        }
//        else {
//            if (!task) Union(param, i);
//            else param = i;
//            task = 0;
//        }
//    }
//    int curpa = findpa(1);
//    Add(curpa);
//    for (int i = 1; i <= n; i++){
//        int u = findpa(i);
//        if (u != curpa){
//            curpa = u;
//            Add(u);
//        }
//    }
//    for (int i = 2; i < d.size(); i++){
//        if (d[i].se > 0 && d[i-2].se > 0){
//            g.pb({d[i].fi, d[i - 2].fi, d[i].se + d[i].se });
//        }
//    }
//}
pair<int, int> dp[N + 1][2];

bool check(int res) {
	dp[0][0] = {0, 0}, dp[0][1] = {-inf, 0};
	for (int i = 1; i <= n; ++i) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		dp[i][1] =
		    max(make_pair(dp[i - 1][1].fi + a[i], dp[i - 1][1].se),
		        make_pair(dp[i - 1][0].fi + a[i] - res, dp[i - 1][0].se + 1));
	}
	return max(dp[n][0], dp[n][1]).se >= k;
};
void solve(){
    
    int l = 0, r = 1e14;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	int res = l;
	check(res);
	cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    #define nametask "PRESUFF"
    if(fopen(nametask".inp", "r")) {
        freopen(nametask".inp", "r", stdin);
        freopen(nametask".out", "w", stdout);
    }
    init();
//    if (ifsub1()) return sub1(), 0;
//    if (ifsub2()) return sub2(), 0;
//    if (k == 1) return sub3(), 0;
//    if (k <= n && n <= 2000) return sub6(), 0;
    solve();
    return 0;
}
/// Duong Anh Kiet from Kien Giang ///
/*
6 1
-1 -2 -1 2 -1 2
*/

Compilation message

feast.cpp: In function 'void solve()':
feast.cpp:151:45: error: no matching function for call to 'max(long long int&, std::pair<long long int, long long int>&)'
  151 |  cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
      |                                             ^
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 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:151:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::pair<long long int, long long int>')
  151 |  cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
      |                                             ^
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 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:151:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::pair<long long int, long long int>')
  151 |  cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
      |                                             ^
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:151:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  151 |  cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
      |                                             ^
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:151:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  151 |  cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
      |                                             ^
feast.cpp: In function 'int main()':
feast.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(nametask".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(nametask".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~