Submission #1103137

#TimeUsernameProblemLanguageResultExecution timeMemory
1103137joyboy23tiFeast (NOI19_feast)C++14
0 / 100
321 ms262144 KiB
#include <bits/stdc++.h> #define fi first #define se second #define FOR(i,l,r) for (int i = l; i <= r; i++) #define FORD(i,l,r) for (int i = l; i >= r; i--) #define el cout <<"\n" #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define MASK(i) ((1LL)<<(i)) #define BIT(x,i) (((x)>>(i))&(1LL)) #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> vii; typedef unsigned long long ull; typedef vector<vector<int>> vvi; int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; } const int N=1e6+5; const int base=311; const int mod=1e9+7; const long long INF=1e18+7; const int d4x[4] = {-1, 0, 1, 0}, d4y[4] = {0, 1, 0, -1}; const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1}; template<class X, class Y> bool maximize(X &x, Y y) { if (x < y) { x = y; return true; } return false; }; template<class X, class Y> bool minimize(X &x, Y y) { if (x > y) { x = y; return true; } return false; }; void add(int &x, int y) { x += y; if (x>=mod) x-=mod; } void sub(int &x, int y) { x -= y; if (x<0) x+=mod; } int mul(int x, int y) { return 1LL * x * y % mod; } int calPw(int x, int y) { int ans = 1; while(y) { if (y&1) ans = 1LL * ans * x % mod; x = 1LL * x * x % mod; y >>= 1; } return ans; } ///KhengmepfromLTVHSFTG int n,a[N],k; ll pre[N]; vector<ll>dp[N]; bool check=true,check2=true; void khengmep() { if(check==true) { ll sum=0; for(int i=1; i<=n; i++) { sum+=a[i]; } cout<<sum; return; } if(check2==true) { if(k==1) { for(int i=1; i<=n; i++) { if(a[i]<0) { cout<<max(pre[i-1],pre[n]-pre[i-1]-a[i]); return; } } } for(int i=1; i<=n; i++) { if(a[i]<0) { cout<<pre[n]-a[i]; return; } } } for(int i=1; i<=k; i++) { ll maxx=-INF; for(int j=1; j<=n; j++) { maxx=max(maxx,dp[j-1][i-1]-pre[j-1]); dp[j][i]=max(maxx+pre[j],dp[j-1][i]); } } cout<<dp[n][k]; } void ip() { cin>>n>>k; pre[0]=0; for(int i=1; i<=n; i++) { cin>>a[i]; if(check==false&&a[i]<0) check2=false; if(a[i]<0) check=false; pre[i]=pre[i-1]+a[i]; } for(int i=1; i<=n; i++) { for(int i=1; i<=k+5; i++) dp[i].push_back(0); } } int main() { // freopen("BANQUET.inp","r",stdin); // freopen("BANQUET.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); int t=1; //cin>>t; while(t--) { ip(); khengmep(); } 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...