Submission #1113192

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113192	2024-11-16T03:20:13 Z	kzhi	Feast (NOI19_feast)	C++14	Compilation error	0 ms	0 KB

feast

/*
    Author : kmv a.k.a kzhi
    K41 IT CHV
*/
#include <bits/stdc++.h>
using namespace std;


#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a ; i <= b; ++ i)
#define FOD(i,a,b) for (int i = a; i >= b; -- i)


#define BIT(mask,i)       ((mask >> i) & 1)
#define MASK(i)                (1ll << (i))
#define OFFBIT(mask,i)  (mask &~(1ll<<(i)))
#define ONBIT(mask,i) (mask | (1ll << (i)))
#define lg2(x)    (63 - __builtin_clzll(x))
#define c_bit          __builtin_popcountll

#define vi vector < int >
#define all(a) a.begin(), a.end()
#define pb push_back

#define ii pair<int,int>
#define pll pair < ll, ll >
#define fi first
#define se second

#define openfile(TASK) if (fopen(TASK".inp","r"))\
        {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define endl '\n'
#define Faster ios_base::sync_with_stdio(false); \
                        cin.tie(0);  cout.tie(0);

#define mid(l,r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1) | 1)
#define ci const int

template <class X, class Y> bool maximize(X &a, const Y &b){if(a < b) return a = b, true;return false;}
template <class X, class Y> bool minimize(X &a, const Y &b){if(a > b) return a = b, true;return false;}

const int N = 3e5 + 5;
const ll oo = 1e17 + 7;
const int LOG = lg2(N);

int n, k;
int a[N];
ll t[N];

ll sum(int l, int r){
    if (l > r)
        return 0;
    return t[r] - t[l - 1];
}

bool ok1 = 1;
int cnt2 = 0, pos2 = -1;

namespace SUB1{
    ll pt[N];

    void SOLVE(){
        pt[0] = oo;
        ll res = - oo;

        FOR (i, 1, n){
            pt[i] = min(t[i], pt[i - 1]);
            maximize(res, t[i] - pt[i - 1]);
            maximize(res, t[i]);
        }

        maximize(res, 0ll);
        cout << res;
    }
}

namespace SUB6{
    static const int maxN = 2e3 + 5;

    ll dp[maxN][maxN][2];

    ll sol(int i, int cnt, bool ok){
        if (i == n + 1 || cnt == k + 1)
            return 0;
        if (dp[i][cnt][ok] != - oo)
            return dp[i][cnt][ok];
        ll cur = - oo;

        if (!ok){
            maximize(cur, sol(i + 1, cnt, 1) + a[i]);

            maximize(cur, sol(i + 1, cnt, 0));
        }
        else{
            maximize(cur, sol(i + 1, cnt, 1) + a[i]);

            maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
        }

        return dp[i][cnt][ok] = cur;
    }

    void SOLVE(){
        FOR (i, 0, maxN - 1)
            FOR (j, 0, maxN - 1)
                FOR (ok, 0, 1)
                    dp[i][j][ok] = - oo;


        cout << sol(1, 1, 0);
    }
}

namespace FULL {
    pll dp[N][2];

    void calc(int mid){
        dp[1][0] = {0, 0}, dp[1][1] = {a[1] - mid, 1};
        for(int i = 2; i <= n; i++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - mid, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
        }
    }

    void SOLVE(){
        ll l = -1, r = oo;

        while (l + 1 < r){
            ll mid = mid(l, r);
            calc(mid);

            if(max(dp[n][0], dp[n][1]).second >= k)
                l = mid;
            else
                r = mid;
        }

        calc(l);

        cout << l * k + max(dp[n][0], dp[n][1]).fi;
    }
}

void SOLVE(){
    cin >> n >> k;

    FOR (i, 1, n){
        cin >> a[i];
        t[i] = t[i - 1] + a[i];
        if (a[i] < 0){
            ok1 = 0;
            cnt2 ++;
            pos2 = i;
        }
    }

    if (ok1){
        cout << t[n];
        return;
    }

    if (cnt2 == 1){
        if (k >= 2)
            cout << t[n] - a[pos2];
        else
            cout << max({t[n], sum(1, pos2 - 1), sum(pos2 + 1, n)});
        return;
    }

    if (k == 1){
        SUB1 :: SOLVE();
        return;
    }

    if (n <= 2000 && k <= 2000){
        SUB6 :: SOLVE();
        return;
    }

    FULL :: SOLVE();
}

signed main(){
    Faster
    openfile("feast")

    int q = 1;

//    cin >> q;

    while (q --){
        SOLVE();
    }

    return 0;
}

Compilation message

feast.cpp: In function 'long long int SUB6::sol(long long int, long long int, bool)':
feast.cpp:100:63: error: no matching function for call to 'max(long long int&, int)'
  100 |             maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
      |                                                               ^
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:5:
/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:100:63: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  100 |             maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
      |                                                               ^
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:5:
/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:100:63: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  100 |             maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
      |                                                               ^
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:5:
/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:100:63: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  100 |             maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
      |                                                               ^
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:5:
/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:100:63: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  100 |             maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
      |                                                               ^
feast.cpp: In function 'int main()':
feast.cpp:32:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:188:5: note: in expansion of macro 'openfile'
  188 |     openfile("feast")
      |     ^~~~~~~~
feast.cpp:32:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:188:5: note: in expansion of macro 'openfile'
  188 |     openfile("feast")
      |     ^~~~~~~~