답안 #1002883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002883	2024-06-19T21:00:37 Z	Lobo	Cigle (COI21_cigle)	C++17	20 / 100	1000 ms	2476 KB

cigle

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e18+10;

int32_t main() {
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	int n;
	cin >> n;
	vector<int> a(n+10);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	vector<vector<int>> dp(n+10,vector<int>(n+10,-inf));
	
	for(int i = 1; i <= n; i++) dp[1][i] = 0;
	int ans = 0;

	for(int j = 1; j <= n; j++) {
		for(int i = 1; i <= j; i++) {
			set<int> sij;
			int sum = 0;
			for(int x = i; x < j; x++) {
				sum+= a[x];
				sij.insert(sum);
			}
			for(int k = 1; k <= i-1; k++) {
				int sm = 0;
				int qtd = 0;
				for(int x = i-1; x > k; x--) {
					sm+= a[x];
					if(sij.count(sm)) qtd++;
				}
				dp[i][j] = max(dp[i][j],dp[k][i-1]+qtd);
			}
		}
	}

	for(int i = 1; i <= n; i++) {
		ans = max(ans,dp[i][n]);
	}
	cout << ans << endl;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	Correct	0 ms	436 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	Correct	0 ms	436 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	8 ms	348 KB	Output is correct
11	Correct	8 ms	348 KB	Output is correct
12	Correct	8 ms	504 KB	Output is correct
13	Correct	9 ms	512 KB	Output is correct
14	Correct	9 ms	348 KB	Output is correct
15	Correct	8 ms	348 KB	Output is correct
16	Correct	9 ms	348 KB	Output is correct
17	Correct	8 ms	348 KB	Output is correct
18	Correct	10 ms	508 KB	Output is correct
19	Correct	8 ms	348 KB	Output is correct
20	Correct	8 ms	508 KB	Output is correct

Subtask #3

0 / 13.0

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

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	Correct	0 ms	436 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	8 ms	348 KB	Output is correct
11	Correct	8 ms	348 KB	Output is correct
12	Correct	8 ms	504 KB	Output is correct
13	Correct	9 ms	512 KB	Output is correct
14	Correct	9 ms	348 KB	Output is correct
15	Correct	8 ms	348 KB	Output is correct
16	Correct	9 ms	348 KB	Output is correct
17	Correct	8 ms	348 KB	Output is correct
18	Correct	10 ms	508 KB	Output is correct
19	Correct	8 ms	348 KB	Output is correct
20	Correct	8 ms	508 KB	Output is correct
21	Execution timed out	1033 ms	2476 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	Correct	0 ms	436 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	8 ms	348 KB	Output is correct
11	Correct	8 ms	348 KB	Output is correct
12	Correct	8 ms	504 KB	Output is correct
13	Correct	9 ms	512 KB	Output is correct
14	Correct	9 ms	348 KB	Output is correct
15	Correct	8 ms	348 KB	Output is correct
16	Correct	9 ms	348 KB	Output is correct
17	Correct	8 ms	348 KB	Output is correct
18	Correct	10 ms	508 KB	Output is correct
19	Correct	8 ms	348 KB	Output is correct
20	Correct	8 ms	508 KB	Output is correct
21	Execution timed out	1033 ms	2476 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-