oj.uz

답안 #1002846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002846 2024-06-19T20:31:44 Z Juan Cigle (COI21_cigle) C++17
0 / 100
 1000 ms 2324 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e3+5;

int p[maxn], dp[maxn][maxn];
bool mark[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++) if(2*p[c]-p[i]<maxn*maxn) rt += mark[2*p[c]-p[i]];
	for(int i=l; i<c; i++) mark[p[i]]=false;
	return rt;
}

signed 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=6;
	bool dbg_on=false;
	int ans=0;
	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 && dbg_on) cout << val << " ";
				dp[i][k+1] = max(dp[i][k+1], dp[k][j]+val);
				ans = max(ans,dp[i][k+1]);
			}
			if(i==dbg && dbg_on) cout << endl;
		}
		if(i==dbg && dbg_on) 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';
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 448 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 1 ms 448 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 448 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 1 ms 448 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 2324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 448 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 1 ms 448 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 448 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 1 ms 448 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -