oj.uz

Submission #848160

# Submission time Handle Problem Language Result Execution time Memory
848160 2023-09-11T13:01:41 Z hehege Feast (NOI19_feast) C++14
0 / 100
 349 ms 252752 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e5 + 9;
const int N2 = 5e3 + 9;
const int INF = 1e18 + 9;

int n, k, a[N], ps[N], f[N], pre[N2], dp[N2][N2];

namespace sub1 {
	bool valid (){
		for (int i = 1; i <= n; i++) if (a[i] < 0) return 0;
		return 1;
	}
	
	void solve (){
		int res = 0;
		for (int i = 1; i <= n; i++) res += a[i];
		cout << res;
	}
}

namespace sub2 {
	bool valid (){
		int x = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) x++;
			if (x >= 2) break;
		}
		return x <= 1;
	}
	
	void solve (){
		int sum1 = 0, sum2 = 0, sumall = 0;
		bool flag = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) flag = 1;
			else if (flag == 0) sum1 += a[i];
			else sum2 += a[i];
		}
		for (int i = 1; i <= n; i++) sumall += a[i];
		if (k == 1) cout << max (sum1, max (sum2, sumall));
		else cout << sum1 + sum2;
	}
}

namespace sub3 {
	bool valid (){
		return k == 1;
	}
	
	void solve (){
		for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
		f[n] = ps[n];
		for (int i = n - 1; i >= 1; i--) f[i] = max (f[i + 1], ps[i]);
		int res = 0;
		for (int i = 1; i <= n; i++) res = max (res, f[i] - ps[i - 1]);
		cout << res;
	}
}

namespace sub45 {
	bool valid (){
		return n <= 500;
	}
	
	void solve (){
		dp[1][1] = max (0LL, a[1]);
    	int res = max (0LL, a[1]);
    	for (int i = 2; i <= n; i++){
    		for (int j = 1; j <= k; j++){
    			if (j > i) continue;
    			dp[i][j] = max (dp[i][j], dp[i - 1][j] + a[i]);
    			for (int k = 1; k < i; k++) dp[i][j] = max (dp[i][j], dp[k][j - 1] + a[i]);
    			res = max (res, dp[i][j]);
    		}
    	}
    	cout << res;
	}
}

void sub6 (){
	dp[1][1] = max (0LL, a[1]);
    pre[1] = max (0LL, a[1]);
    int res = max (0LL, a[1]);
    for (int i = 2; i <= n; i++){
    	for (int j = 1; j <= k; j++){
    		if (j > i) continue;
    		dp[i][j] = max (dp[i][j], max (dp[i - 1][j] + a[i], pre[j - 1] + a[i]));
    		pre[j] = max (pre[j], dp[i][j]);
    		res = max (res, dp[i][j]);
    	}
    }
    cout << res;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sub6 ();
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 252752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 54864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 54864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Incorrect 1 ms 4696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Incorrect 1 ms 4696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Incorrect 1 ms 4696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 252752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -