oj.uz

Submission #1002702

# Submission time Handle Problem Language Result Execution time Memory
1002702 2024-06-19T18:23:18 Z Sofiatpc Cigle (COI21_cigle) C++14
0 / 100
 929 ms 1568 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505;
int dp[MAXN][MAXN], dp1[MAXN], d[MAXN], sp[MAXN];

int sum(int i, int j){
	return sp[j] - sp[i-1];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n; cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>d[i];
		sp[i] = sp[i-1]+d[i];
	}

	int ans = 0;
	for(int l = n-1; l >= 1; l--)
		for(int r = l; r < n; r++){
			set<int> st; 
			for(int i = l; i < r; i++)st.insert(sum(i+1,r));

			//cout<<l<<" "<<r<<": ";
			//for(int x : st)cout<<x<<" "; cout<<" | ";

			int qtd = 0;
			for(int j = r+1; j < n; j++)
				if(st.find(sum(r+1,j)) != st.end()){
					qtd++;
					dp[l][r] = max(dp[l][r], dp1[r+1]+qtd);
				}
			//cout<<dp[l][r]<<" ";
				
			//cout<<qtd<<"\n";
			ans = max(ans,dp[l][r]);
			dp1[l] = max(dp1[l],dp[l][r]);
		}
		
	cout<<ans<<"\n";
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 929 ms 1568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

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

Subtask #5
0 / 52.0

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