Submission #848129

#	Time	Username	Problem	Language	Result	Execution time	Memory
848129		asd12343	Feast (NOI19_feast)	C++14	0 / 100	2 ms	532 KiB

feast

#pragma GCC optimize("Os")
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e6+5;
const int INF = 0x3f3f3f3f;
#define int long long
#define pb push_back
#define p make_pair	
#define fi first
#define se second
#define pii pair<int,int>
#define f(i,a,b) for (int i = a ; i < b ; i++)
#define f1(i,a,b) for (int i = a ; i > b ; i--)
#define f2(i,a,b) for (int i = a ; i <= b ; i++)
#define FILE(X)						\
	freopen(#X ".INP","r",stdin);	\
	freopen(#X ".OUT","w",stdout);

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r) { return l + rd() % (r - l + 1); }
int a[MN];
int n,k,pos;
int cnt = 0;
int dp[5003][5003];
signed main(){
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    FILE(BLUESKY);
    bool flag = false;
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i++) {
    	cin >> a[i];
    	if (a[i] < 0) flag = true,cnt++, pos = i;
    }	
    if (flag == false) cout << accumulate(a+1,a+n+1,0LL);
    else if (cnt == 1) {
    	if (k == 1) {
    		int sum = 0, sum2 = 0;
    		for (int i = 1 ; i < pos ; i++) sum += a[i];
    		for (int i = pos+1 ; i <= n ; i++) sum2 += a[i];
    		cout << max(sum,sum2) << "\n";
    	}
    	else {
    		cout << accumulate(a+1,a+n+1,0LL) - a[pos];
    	}
    }
    else if (cnt == n) cout << 0;
    else if (n <= 5000) {
    	for (int i = 0 ; i <= n ; i++) dp[i][1] = 0;
    	for (int i = 1 ; i <= n ; i++) {
    		for (int j = 0 ; j <= k ; j++) { 
    			dp[i][j+1] = max(dp[i][j+1],dp[i-1][j]);
    			dp[i][j] = max(dp[i][j],dp[i-1][j] + a[i]);
    		}
    	}
    	int ans = 0;
    	for (int i = 0 ; i <= k ; i++) ans = max(ans,dp[n][i]);
    	cout << ans <<"\n";
    }
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen(#X ".INP","r",stdin); \
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
feast.cpp:28:5: note: in expansion of macro 'FILE'
   28 |     FILE(BLUESKY);
      |     ^~~~
feast.cpp:17:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  freopen(#X ".OUT","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:28:5: note: in expansion of macro 'FILE'
   28 |     FILE(BLUESKY);
      |     ^~~~

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