Submission #1103122

#TimeUsernameProblemLanguageResultExecution timeMemory
1103122khoaha123Feast (NOI19_feast)C++14
40 / 100
1080 ms224116 KiB
#include <bits/stdc++.h> #define endl '\n' #define ii pair<int,int> #define task "" #define all(x) x.begin(),x.end() #define MASK(x) (1 << (x)) #define int long long using namespace std; const int N = 3e5 + 5; const int LOG = 20; const int mod = 998244353; const long long INF = 1e18; int n,a[N],dp[305][305][305],s[N]; int calc(int l,int r,int k){ if (k == 0) return 0; if (l == r) return max(a[l],0LL); int &res = dp[l][r][k]; if (res != -1) return res; res = 0; for (int i = l; i < r; ++i){ for (int j = 0; j <= min(k,(i-l+1)); ++j){ res = max(res,calc(l,i,j) + calc(i+1,r,k-j)); } } res = max(res,s[r] - s[l-1]); return res; } int k; void subtask1(void){ int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i]; cout << sum; } void subtask2(void){ int pos = -1; for (int i = 1; i <= n; ++i){ if (a[i] < 0){ pos = i;break; } } if (pos == -1){ subtask1();return; } int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i]; if (k == 1){ int sum1 = 0,sum2 = 0; for (int i = 1; i < pos; ++i) sum1 += a[i]; for (int i = pos+1; i <= n; ++i) sum2 += a[i]; cout << max(sum1,max(sum2,sum)); } else { cout << max(sum,sum - a[pos]); } } void subtask3(void){ int best = 0; int sum = 0; for (int i = 1; i <= n; ++i){ sum = max(a[i],sum + a[i]); best = max(best,sum); } cout << best; } void subtask4(void){ memset(dp,-1,sizeof(dp)); cout << calc(1,n,k) << endl; } long long Rand(long long l, long long r) { long long res = 0; for (int i= 1; i <= 4; ++i) res = (res << 15) ^ (rand() & ((1 << 15) - 1)); return l + res % (r-l+1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); if (fopen(task".INP","r")){ freopen(task".INP","r",stdin); freopen(task".OUT","w",stdout); } srand(time(NULL)); cin >> n >> k; int sub1 = 0,am = 0; for (int i = 1; i <= n; ++i){ cin >> a[i]; //a[i] = Rand(-1000000000,1000000000); if (a[i] >= 0) sub1++; else am++; s[i] = s[i-1] + a[i]; } if (sub1 == n){ subtask1(); return 0; } if (k == 1){ subtask3(); return 0; } if (am == 1){ subtask2(); return 0; } subtask4(); return 0; }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...