Submission #1211903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211903		davele	Feast (NOI19_feast)	C++20	100 / 100	85 ms	2632 KiB

feast

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

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

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "feast";
const int lim = 3e5, limit = lim+5, inf = 1e18;

int n, k;
int A[limit];
//

pii get (int lambda){
    // first : maximum sum
    // second : tra ve so luong doan
    //
    // 1: dang xet doan lien tiep
    // 0: da dung xet doan lien tiep
    pii dp[2];
    dp[0] = {0, 0};
    dp[1] = {-inf, 1};
    for (int i=1; i<=n; i++){
        dp[1].fi+=A[i];
        maximize(dp[1], make_pair (dp[0].fi+A[i]-lambda, dp[0].se+1));
        maximize(dp[0], dp[1]);
    }
    return max (dp[0], dp[1]);
}

//

void process(){
    int l = 0, r = (int)(1e12);
    int ret = 0;
    while (l<=r){
        int mid = (l+r)/2;
        pii tmp = get (mid);
//        cerr<<mid<<" "<<tmp.se<<"\n";
        if (tmp.se<=k){
            r = mid-1;
            ret = tmp.fi + tmp.se*mid;
        }
        else l = mid+1;
    }
    cout<<ret;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
    if (fopen((name+".inp").c_str(), "r")){
        freopen ((name+".inp").c_str(), "r", stdin);
        freopen ((name+".out").c_str(), "w", stdout);
    }
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>A[i];
    process();
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:118:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen ((name+".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:119:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen ((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29