Submission #759765

#	Time	Username	Problem	Language	Result	Execution time	Memory
759765		jay_jayjay	Feast (NOI19_feast)	C++14	59 / 100	138 ms	262144 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);
        //printf("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]);
                        //printf("x=%lld a[i]=%d\n",x,a[i]);
                        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]);
                        //printf("dp[%d][%d]=%lld\n",k,i,dp[k][i]);
                }
        }
        printf("%lld\n",dp[nk][n-1]);
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:34:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         int n,nk;scanf("%d %d",&n,&nk);
      |                  ~~~~~^~~~~~~~~~~~~~~~
feast.cpp:36:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         vector<int> a(n);for(auto&x:a)scanf("%d",&x);
      |                                       ~~~~~^~~~~~~~~

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