Submission #863146

#	Time	Username	Problem	Language	Result	Execution time	Memory
863146		MilosMilutinovic	Feast (NOI19_feast)	C++14	100 / 100	134 ms	14164 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=303000;
int n,k,a[N];
pair<ll,int> dp[N][2];

pair<ll,int> solve(ll cst) {
    dp[0][0]=mp(0,0);
    dp[0][1]=mp(-1e17,0);
    rep(i,1,n+1) {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=max(mp(dp[i-1][1].fi+a[i],dp[i-1][1].se),mp(dp[i-1][0].fi+a[i]-cst,dp[i-1][0].se-1));
    }
    pair<ll,int> ans=max(dp[n][0],dp[n][1]);
    return {ans.fi,-ans.se};
}

int main() {
    scanf("%d%d",&n,&k);
    rep(i,1,n+1) scanf("%d",a+i);
    ll l=0,r=1e15,lmb=0;
    while (l<=r) {
        ll mid=l+r>>1;
        if (solve(mid).se<=k) {
            lmb=mid;
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    pair<ll,int> ans=solve(lmb);
    printf("%lld\n",ans.fi+ans.se*lmb);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         ll mid=l+r>>1;
      |                ~^~
feast.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
feast.cpp:41:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     rep(i,1,n+1) scanf("%d",a+i);
      |                  ~~~~~^~~~~~~~~~

• 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