oj.uz

Submission #975506

# Submission time Handle Problem Language Result Execution time Memory
975506 2024-05-05T11:12:09 Z Nexus Split the sequence (APIO14_sequence) C++17
0 / 100
 3 ms 3676 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N=1e3+9,M=2e18+9,mod=1e9+7;

ll a[N],s[N],dp[N][209],p[N][209],n,k,x,y,z,o;
vector<ll>v;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>k;
	for(ll i=1;i<=n;++i)cin>>a[i];
	
	for(ll i=n;i;--i)s[i]=a[i]+s[i+1];
	
	for(ll i=1;i<n;++i)
	dp[i][1]=(s[1]-s[i+1])*s[i+1],p[i][1]=i;
	
	for(ll j=2;j<=k;++j)
	{
		for(ll i=j;i<=n;++i)
		{
			x=dp[j-1][j-1]+(a[j])*s[i+1],y=j;
			for(ll g=j-1;g<i;++g)
			{
				if(dp[g][j-1]+(s[g+1]-s[i+1])*s[i+1]>x)
				x=dp[g][j-1]+(s[g+1]-s[i+1])*s[i+1],y=g;
			}
			dp[i][j]=x,p[i][j]=y;
			if(x>o)o=x,z=i;
		}
	}
	
	/*
	for(ll i=1;i<=n;++i)
	{
		for(ll j=1;j<=k;++j)
		cout<<dp[i][j]<<' ';
		cout<<'\n';
	}
	*/
	
	cout<<dp[z][k]<<'\n';
	
	x=z;
	for(ll i=k;i;--i)
	{
		v.push_back(x);
		x=p[x][i];
	}
	
	reverse(v.begin(),v.end());
	for(auto i:v)cout<<i<<' ';
	
}

/*
7 3
4 1 3 4 0 2 3

108
1 3 5
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 108 == 108
2 Correct 3 ms 2396 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 2396 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB contestant found the optimal answer: 1093956 == 1093956
2 Incorrect 1 ms 2396 KB position 3 occurs twice in split scheme
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2524 KB contestant found the optimal answer: 610590000 == 610590000
2 Incorrect 1 ms 2652 KB position 3 occurs twice in split scheme
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB contestant found the optimal answer: 21503404 == 21503404
2 Incorrect 2 ms 3676 KB position 2 occurs twice in split scheme
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -