이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;const int N=510,M=5009;
pair<int,int>dp[N][N];int a[N],fr[M],rw[N][N][N],prf[M];
pair<int,int>mxdp[N][N];
int main()
{
cin>>n;int ans=0;
for(int i=1;i<n+1;i++)cin>>a[i];
for(int i=2;i<n;i++)
{
int sm=0;
for(int j=i+1;j<n+1;j++)
{
if(j!=i+1)
{
sm+=a[j-1];
fr[sm]=1;
}
int s=0,rs=0;
for(int q=i-1;q>-1;q--)
{
if(q!=i-1)
{
s+=a[q+2];
if(fr[s])
rs++;
}
rw[q][i][j]=rs;
}
}
for(int j=n;j>i;j--)
{
if(j!=i+1)
{
fr[sm]=0;
sm-=a[j-1];
}
}
}
for(int m=1;m<=n;m++)
{
memset(prf,-1,sizeof prf);
int re=0;
for(int i=m;i>0;i--)
{
re+=a[i];
prf[re]=i;
}
re=0;
dp[m][m]={0,n+1};
mxdp[m][1]={dp[m][1].fi,1};
for(int i=2;i<m;i++)
{
if(dp[m][i].fi>mxdp[m][i-1].fi)
{
mxdp[m][i]={dp[m][i].fi,i};continue;
}
mxdp[m][i]=mxdp[m][i-1];
}
dp[m+1][m]=mxdp[m][m-1];
for(int r=m+2;r<n+1;r++)
{re+=a[r-1];
int last=dp[r-1][m].se;
int mx=dp[r-1][m].fi;
if(prf[re]==-1||prf[re]-2<0)
{
dp[r][m]=dp[r-1][m];
ans=max(ans,dp[r][m].fi);continue;
}
if(last+2<=prf[re])
{
dp[r][m]={mx+1,last};
ans=max(ans,dp[r][m].fi);continue;
}
pair<int,int>z=mxdp[m][prf[re]-2];
z.fi+=rw[prf[re]-2][m][r];
if(z.fi>mx)
{
dp[r][m]=z;
ans=max(ans,z.fi);continue;
}
dp[r][m]=dp[r-1][m];
ans=max(ans,dp[r][m].fi);
continue;
}
}
cout<<ans;
}
/*
10
2 3 2 1 1 5 5 2 5 1
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |