oj.uz

Submission #707972

# Submission time Handle Problem Language Result Execution time Memory
707972 2023-03-10T15:57:08 Z arcane Cigle (COI21_cigle) C++17
0 / 100
 4 ms 4180 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, ptr, cnt, ans = 0; cin >> n;
	int arr[n], dp[n][n], pref[n][n], prefs[n + 1]; for (int i = 0; i < n; i++) cin >> arr[i];
	prefs[0] = 0; for (int i = 0; i < n; i++) prefs[i + 1] = prefs[i] + arr[i];
	for (int i = 1; i < n; i++) fill(dp[i], dp[i] + n, 0);
	fill(dp[0], dp[0] + n, 0);
	for (int i = 1; i < n; i++){
		ptr = i - 1; cnt = 0;
		for (int j = 0; j < n; j++){
			if (!j) pref[i - 1][j] = dp[j][i - 1];
			else pref[i - 1][j] = max(dp[j][i - 1], pref[i - 1][j - 1]);
		}
		for (int j = i; j < n; j++){
			if (j == i) dp[i][j] = pref[i - 1][i - 1];
			else{
				dp[i][j] = dp[i][j - 1];
				while (ptr >= 0 and prefs[i] - prefs[ptr + 1] <= prefs[j] - prefs[i]){
					if (prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]) cnt += 1;
					dp[i][j] = max(dp[i][j], dp[ptr][i - 1] + cnt);
					ptr--;
				}
			} 
		}
	}
	for (int i = 0; i < n; i++) ans = max(ans, dp[i][n - 1]);
	cout << ans << '\n';
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 52.0

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