Submission #759822

#	Time	Username	Problem	Language	Result	Execution time	Memory
759822		jay_jayjay	Feast (NOI19_feast)	C++14	100 / 100	294 ms	14092 KiB

feast

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <deque>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f
#define ninf 0xbebebebe
#define ninfl 0xbebebebebebebebe

#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#include <assert.h>
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#define assert(args...) 42
#endif
// 1}}}


int main()
{
        int n,nk;scanf("%d %d",&n,&nk);
        dprintf("n=%d nk=%d\n",n,nk);
        vector<int> a(n);for(auto&x:a)scanf("%d",&x);

        /*
        vector<vector<ll>> dp(nk+1, vector<ll>(n,0));

        for(int i=0;i<n;i++)dp[0][i] = 0;
        for(int k=1;k<=nk;k++) {
                ll x=0;
                for(int i=0;i<n;i++) {
                        if(i)x = max(x,dp[k-1][i-1]);
                        dp[k][i] = (x += a[i]);
                        if(i) dp[k][i] = max(dp[k][i],dp[k][i-1]);
                        else dp[k][i] = max(0ll,dp[k][i]);
                }
        }
        */

        auto dp = [&](ll B) {
                vector<ll> dp(n), cnt(n);
                /* let dp_B [i] = best cost for [0...i]
                //               given cnt[i] subarrays,
                //               where each subarray costs B
                //
                // dp\[-1] = 0
                // dp\[i] = max( dp\[i-1], -\ + max [j<=i] (dp\[j-1] + sum a_j..i ) )
                */

                ll x=0,cx=0; // represents max[j<=i] dp[j-1]+sum a_j..i
                for(int i=0;i<n;i++) {
                        dp[i] = i?dp[i-1]:0; cnt[i]=i?cnt[i-1]:0;
                        x+=a[i];
                        //printf("x=%lld cx=%lld B=%lld x-B=%lld\n",x,cx,B,x-B);
                        if(x-B > dp[i]) dp[i]=x-B, cnt[i]=cx+1;
                        if(dp[i]>x) x=dp[i],cx=cnt[i];
                        //dp[i] = max(i?dp[i-1]:0, (x+=a[i]) - B);
                        //x=max(x, dp[i]);
                        //printf("i=%d dp=%lld cnt=%lld\n",i,dp[i],cnt[i]);
                }
                //printf("n-1=%d dp=%lld cnt=%lld\n",n-1,dp[n-1],cnt[n-1]);
                return pair<vector<ll>,vector<ll>>{dp, cnt};
        };
        ll lB = 0, rB = 1e18;
        while(lB<rB) {
                ll mB = lB+(rB-lB)/2;
                dprintf("B %lld %lld %lld\n",lB,mB,rB);
                auto [Bdp, cnt] = dp(mB);
                dprintf("cnt %lld\n",cnt[n-1]);
                if(cnt[n-1] > nk) lB=mB+1;
                else rB=mB;
        }

        auto [Bdp, cnt] = dp(lB);
        //for(auto x:Bdp)printf("%lld ",x);printf("\n");
        //for(auto x:cnt)printf("%lld ",x);printf("\n");
        dprintf("%lld %lld %lld\n",Bdp[n-1],lB,nk);
        printf("%lld\n",Bdp[n-1] + lB * nk);

        //printf("%lld\n",dp[nk][n-1]);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:27:26: warning: statement has no effect [-Wunused-value]
   27 | #define dprintf(args...) 69
      |                          ^~
feast.cpp:36:9: note: in expansion of macro 'dprintf'
   36 |         dprintf("n=%d nk=%d\n",n,nk);
      |         ^~~~~~~
feast.cpp:27:26: warning: statement has no effect [-Wunused-value]
   27 | #define dprintf(args...) 69
      |                          ^~
feast.cpp:81:17: note: in expansion of macro 'dprintf'
   81 |                 dprintf("B %lld %lld %lld\n",lB,mB,rB);
      |                 ^~~~~~~
feast.cpp:82:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |                 auto [Bdp, cnt] = dp(mB);
      |                      ^
feast.cpp:27:26: warning: statement has no effect [-Wunused-value]
   27 | #define dprintf(args...) 69
      |                          ^~
feast.cpp:83:17: note: in expansion of macro 'dprintf'
   83 |                 dprintf("cnt %lld\n",cnt[n-1]);
      |                 ^~~~~~~
feast.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         auto [Bdp, cnt] = dp(lB);
      |              ^
feast.cpp:27:26: warning: statement has no effect [-Wunused-value]
   27 | #define dprintf(args...) 69
      |                          ^~
feast.cpp:91:9: note: in expansion of macro 'dprintf'
   91 |         dprintf("%lld %lld %lld\n",Bdp[n-1],lB,nk);
      |         ^~~~~~~
feast.cpp:35:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         int n,nk;scanf("%d %d",&n,&nk);
      |                  ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:37:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         vector<int> a(n);for(auto&x:a)scanf("%d",&x);
      |                                       ~~~~~^~~~~~~~~

• 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