Submission #1101092

#TimeUsernameProblemLanguageResultExecution timeMemory
1101092trieFeast (NOI19_feast)C++17
71 / 100
114 ms104188 KiB
#include<bits/stdc++.h> #define mp make_pair #define fi first #define se second #define ii pair<int, int> #define iii pair<ii, int> #define ll long long #define pb push_back #define pli pair<ll, int> #define all(v) (v).begin(), (v).end() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define cntbit(mask) __builtin_popcount(mask) #define getbit(x, i) ((x >> i) & 1) #define MASK(i) (1 << i) #define pli pair<ll, int> using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;} const int N = 2005; const int V = 3e5 + 5; const int MOD = 1e9 + 7; int n, k; ll pr[V], dp[N][N], mx[N][N], a[V]; int negative, idx; void solve() { cin >> n >> k; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; pr[i] = pr[i - 1] + a[i]; if (a[i] < 0) { negative++; idx = i; } } if (!negative) return cout << pr[n], void(); if (k == 1) { // kadane algorithm. ll sum = 0, mxsum = 0; for(int i = 1 ; i <= n ; i++) { sum += a[i]; maximize(mxsum, sum); if (sum < 0) sum = 0; } return cout << mxsum, void(); } if (negative == 1) return cout << pr[n] - a[idx], void(); for(int i = 1 ; i <= n ; i++) mx[i][0] = max(mx[i - 1][0], - pr[i]); for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) { dp[i][j] = dp[i - 1][j]; maximize(dp[i][j], mx[i][j - 1] + pr[i]); mx[i][j] = max(mx[i - 1][j], dp[i][j] - pr[i]); } cout << dp[n][k]; } int main(void) { //freopen("task.inp", "r", stdin); //freopen("task.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while(t--) solve(); return 0; }
#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...