Submission #966852

#	Time	Username	Problem	Language	Result	Execution time	Memory
966852		jadai007	Feast (NOI19_feast)	C++14	18 / 100	1062 ms	5212 KiB

feast

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n,k, arr[300300], l, r, vis[300300], mx = -1e18, sum, now, ans;

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 1; i<=n; ++i) cin >> arr[i];
    for(int i = 1; i<=k; ++i){
        mx = -1e18;
        int cnt = 0, now = 0, sum = 0;
        for(int j = 1; j<=n; ++j){
            if(vis[j]){
                sum = 0;
                continue;
            }
            sum+=arr[j];
            cnt++;
            if(mx < sum){
                mx = sum;
                now = cnt;
                r = j;
            }
            if(sum < 0){
                sum = 0;
                cnt = 0;
            }
        }
        if(mx > 0) for(int j = r - now + 1; j<=r; ++j) vis[j] = 1;
        ans+=max(0ll, mx);
    }
    cout << ans;
}

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