Submission #1002715

# Submission time Handle Problem Language Result Execution time Memory
1002715 2024-06-19T18:33:01 Z Juan Cigle (COI21_cigle) C++17
0 / 100
1000 ms 1876 KB
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+5;

int p[maxn], dp[maxn][maxn];
bool mark[2*maxn*maxn];

int calc(int r, int l, int c){
	int rt=0;
	for(int i=l; i<c; i++) mark[p[i]]=true;
	for(int i=c+1; i<r; i++) rt += mark[2*p[c]-p[i]];
	for(int i=l; i<c; i++) mark[p[i]]=false;
	return rt;
}

int main(){
	int n; cin >> n;
	vector<int> v(n+1);
	for(int i=1; i<=n; i++) cin >> v[i];
	for(int i=1; i<=n; i++) p[i] = p[i-1]+v[i];

	int dbg=12;
	for(int i=1; i<=n; i++){
		for(int j=1; j<i; j++){
			for(int k=j; k<i; k++){
				int val = calc(i,j,k);
				// if(i==dbg) cout << val << " ";
				dp[i][k+1] = max(dp[i][k+1], dp[k][j]+val);
			}
			// if(i==dbg) cout << endl;
		}
		// if(i==dbg) cout << endl;
	}

	// for(int i=0; i<=n; i++) cout << dp[i] << " ";
	// cout << endl;

	int ans=0;
	for(int i=0; i<=n; i++) ans = max(ans,dp[n][i]);
	cout << ans << '\n';
	// cout << dp[n] << '\n';
}

Compilation message

cigle.cpp: In function 'int main()':
cigle.cpp:22:6: warning: unused variable 'dbg' [-Wunused-variable]
   22 |  int dbg=12;
      |      ^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 1876 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -