Submission #1277982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277982		namhh	Cigle (COI21_cigle)	C++20	0 / 100	4 ms	5256 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e3+5;
int n,a[N],dp[N][N],pre[N][N],check[N*N];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++){
    	int cur = 0;
    	for(int j = i-1; j >= 2; j--){
    		cur += a[j];
    		check[cur] = 1;
		}
		int l = i-1;
		int cur1 = 0;
		int cur2 = 0;
		int cnt = 0;
		bool ck = true;
		for(int j = i; j <= n; j++){
			while(cur2 <= cur1){
				if(l == 0){
					ck = false;
					break;
				}
				cur2 += a[l];
				l--;
			}
			if(ck == false) break;
			dp[i][j] = pre[i-1][l+1]+cnt;
			cur1 += a[j];
			if(check[cur1]) cnt++;
		}
		cur = 0;
		for(int j = i-1; j >= 2; j--){
    		cur += a[j];
    		check[cur] = 0;
		}
		for(int j = 1; j <= i; j++) pre[i][j] = max(pre[i][j-1],dp[j][i]);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) ans = max(ans,dp[i][n]);
	cout << ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52