oj.uz

Submission #1003614

# Submission time Handle Problem Language Result Execution time Memory
1003614 2024-06-20T13:57:16 Z Lalic Cigle (COI21_cigle) C++17
0 / 100
 3 ms 5468 KB 
#include <bits/stdc++.h>
#pragma GCC optimize "Ofast,unroll-loops"
#pragma GCC target "avx2"
using namespace std;

const int MAXN = 5005;

int dp[MAXN][MAXN], pref[MAXN][MAXN];

void solve(){
	int n; cin >> n;
	
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++) cin >> arr[i];
	
	vector<int> ps(n+1); ps[0]=0;
	for(int i=1;i<=n;i++) ps[i]+=ps[i-1]+arr[i];
	
	for(int l=2;l<=n;l++){
		int ptr=l-1, sum=0, curr=0, tot=0;
		for(int r=l;r<=n;r++){
			dp[l][r]=max(dp[l][r-1], pref[ptr][l-1]+tot);
			sum+=arr[r];
			while(ptr>0 && curr<sum) curr+=arr[ptr--];
			tot+=(curr==sum);
		}
		
		pref[0][l]=dp[0][l];
		for(int i=1;i<=l;i++) pref[i][l]=max(dp[i][l], pref[i-1][l]);
	}
	
	int ans=pref[n][n];
	cout << ans << "\n";
}


int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5464 KB Output is correct
2 Incorrect 3 ms 5468 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 600 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

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