Submission #1164963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164963		son2008	Feast (NOI19_feast)	C++20	100 / 100	101 ms	12188 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e5+5;
const int mod=1e9+7;
int n,k,a[maxn];
ii dp[maxn][2];
void init()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
}
bool check(int mid)
{
    dp[0][1]={-1e18,0};
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=max(mp(dp[i-1][0].fi+a[i]-mid,dp[i-1][0].se+1),mp(dp[i-1][1].fi+a[i],dp[i-1][1].se));
    }
    ii ans=max(dp[n][0],dp[n][1]);
    return ans.se>=k;
}
void process()
{
    int l=0,r=1e15,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    check(ans);
    ii sum=max(dp[n][0],dp[n][1]);
    cout<<sum.fi+k*ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(task".out","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