답안 #1116183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116183	2024-11-21T10:15:04 Z	NotLinux	Cigle (COI21_cigle)	C++17	9 / 100	90 ms	100168 KB

cigle

// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 5e3 * 5e3 + 7;
const int inf = 1e9 + 7;
void solve(){
	int n;
	cin >> n;
	int arr[n] , pre[n+1] , cnt[N];
	memset(cnt , -1 , sizeof(cnt));
	pre[0] = 0;
	cnt[0] = -1;
	for(int i = 0;i<n;i++){
		cin >> arr[i];
		pre[i+1] = pre[i] + arr[i];
		cnt[pre[i+1]] = i;
	}
	int dp[n+1][n+1] = {0} , maxi[n+1][n+1] = {0};
	for(int j = 2;j<n;j++){
		int sayac = 0;
		for(int i = j+1;i<=n;i++){
			if(2 * pre[j] - pre[i] >= 0 and cnt[2 * pre[j] - pre[i]] != -1){
				sayac++;
				// cout << " aha : " << i << " , " << j << " => " << sayac << " + " << maxi[j][cnt[2 * pre[j] - pre[i]]] << endl;
				dp[i+1][j] = max(dp[i+1][j] , maxi[j][cnt[2 * pre[j] - pre[i]]] + sayac);
				// cout << "AHA : " << i << " , " << j << " : " << maxi[j][cnt[2 * pre[j] - pre[i]]] << " tf " << cnt[2 * pre[j] - pre[i]] << endl;
			}
			else{
				dp[i+1][j] = max(dp[i+1][j] , dp[i][j]);	
			}
			maxi[i][j] = max(maxi[i][j-1] , dp[i][j]);
			if(j > 0){
				if(i - j > 1)dp[i+1][i] = max(dp[i+1][i] , dp[i][j]);	
			}
			else{
				if(i > 2)dp[i+1][i] = max(dp[i+1][i] , dp[i][j]);	
			}
			// cout << i << " " << j << " : " << dp[i][j] << endl;
		}
	}
	int ans = 0;
	for(int i = 0;i<n;i++){
		ans = max(ans , dp[n][i]);
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	98124 KB	Output is correct
2	Correct	81 ms	98200 KB	Output is correct
3	Correct	84 ms	98120 KB	Output is correct
4	Correct	85 ms	98240 KB	Output is correct
5	Correct	84 ms	98120 KB	Output is correct
6	Correct	81 ms	98120 KB	Output is correct
7	Correct	79 ms	98124 KB	Output is correct
8	Correct	89 ms	98124 KB	Output is correct
9	Correct	81 ms	98124 KB	Output is correct

Subtask #2

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	98124 KB	Output is correct
2	Correct	81 ms	98200 KB	Output is correct
3	Correct	84 ms	98120 KB	Output is correct
4	Correct	85 ms	98240 KB	Output is correct
5	Correct	84 ms	98120 KB	Output is correct
6	Correct	81 ms	98120 KB	Output is correct
7	Correct	79 ms	98124 KB	Output is correct
8	Correct	89 ms	98124 KB	Output is correct
9	Correct	81 ms	98124 KB	Output is correct
10	Correct	85 ms	98120 KB	Output is correct
11	Correct	81 ms	98200 KB	Output is correct
12	Correct	85 ms	98120 KB	Output is correct
13	Correct	83 ms	98120 KB	Output is correct
14	Correct	84 ms	98208 KB	Output is correct
15	Incorrect	82 ms	98120 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	100060 KB	Output is correct
2	Correct	85 ms	100160 KB	Output is correct
3	Correct	87 ms	100168 KB	Output is correct
4	Correct	81 ms	100168 KB	Output is correct
5	Correct	90 ms	100168 KB	Output is correct
6	Incorrect	86 ms	100168 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	98124 KB	Output is correct
2	Correct	81 ms	98200 KB	Output is correct
3	Correct	84 ms	98120 KB	Output is correct
4	Correct	85 ms	98240 KB	Output is correct
5	Correct	84 ms	98120 KB	Output is correct
6	Correct	81 ms	98120 KB	Output is correct
7	Correct	79 ms	98124 KB	Output is correct
8	Correct	89 ms	98124 KB	Output is correct
9	Correct	81 ms	98124 KB	Output is correct
10	Correct	85 ms	98120 KB	Output is correct
11	Correct	81 ms	98200 KB	Output is correct
12	Correct	85 ms	98120 KB	Output is correct
13	Correct	83 ms	98120 KB	Output is correct
14	Correct	84 ms	98208 KB	Output is correct
15	Incorrect	82 ms	98120 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	98124 KB	Output is correct
2	Correct	81 ms	98200 KB	Output is correct
3	Correct	84 ms	98120 KB	Output is correct
4	Correct	85 ms	98240 KB	Output is correct
5	Correct	84 ms	98120 KB	Output is correct
6	Correct	81 ms	98120 KB	Output is correct
7	Correct	79 ms	98124 KB	Output is correct
8	Correct	89 ms	98124 KB	Output is correct
9	Correct	81 ms	98124 KB	Output is correct
10	Correct	85 ms	98120 KB	Output is correct
11	Correct	81 ms	98200 KB	Output is correct
12	Correct	85 ms	98120 KB	Output is correct
13	Correct	83 ms	98120 KB	Output is correct
14	Correct	84 ms	98208 KB	Output is correct
15	Incorrect	82 ms	98120 KB	Output isn't correct
16	Halted	0 ms	0 KB	-