oj.uz

Submission #337385

# Submission time Handle Problem Language Result Execution time Memory
337385 2020-12-20T13:33:47 Z ogibogi2004 Split the sequence (APIO14_sequence) C++14
22 / 100
 288 ms 35436 KB 
#include<bits/stdc++.h>
using namespace std;
#define move dafds
#define ll long long
const ll INF=2e15;
const ll MAXN=128,MAXK=128;
ll dp[MAXN][MAXN][MAXK];
pair<ll,ll> move[MAXN][MAXN][MAXK];
ll a[MAXN];
ll pref[MAXN];
ll n;
vector<ll>v;
ll solve(ll l,ll r,ll k)
{
	if(k==0)return 0;
	if(dp[l][r][k]!=-1)return dp[l][r][k];
	for(ll i=l;i<r;i++)
	{
		for(int j=0;j<k;j++)
		{
			ll val=(pref[i]-pref[l-1])*(pref[r]-pref[i])+solve(l,i,j)+solve(i+1,r,k-1-j);
			if(val>dp[l][r][k])
			{
				dp[l][r][k]=val;
				move[l][r][k]={i,j};
			}
		}
	}
	return dp[l][r][k];
}
void find_splits(ll l,ll r,ll k)
{
	if(k==0)return;
	v.push_back(move[l][r][k].first);
	find_splits(l,move[l][r][k].first,move[l][r][k].second);
	find_splits(move[l][r][k].first+1,r,k-1-move[l][r][k].second);
}
int main()
{
	ll k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		pref[i]=pref[i-1]+a[i];
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(1,n,k)<<endl;
	find_splits(1,n,k);
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
	cout<<endl;
return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
      |              ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16748 KB contestant found the optimal answer: 108 == 108
2 Correct 9 ms 16748 KB contestant found the optimal answer: 999 == 999
3 Correct 9 ms 16748 KB contestant found the optimal answer: 0 == 0
4 Correct 9 ms 16876 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 9 ms 16876 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 8 ms 16748 KB contestant found the optimal answer: 1 == 1
7 Correct 8 ms 16748 KB contestant found the optimal answer: 1 == 1
8 Correct 9 ms 16748 KB contestant found the optimal answer: 1 == 1
9 Correct 10 ms 17004 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 9 ms 16876 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 9 ms 16876 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 8 ms 16876 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 9 ms 16876 KB contestant found the optimal answer: 140072 == 140072
14 Correct 9 ms 16748 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 9 ms 16876 KB contestant found the optimal answer: 805 == 805
16 Correct 9 ms 16896 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 9 ms 16876 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19308 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 11 ms 19308 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 288 ms 19564 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 10 ms 19308 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 22 ms 19308 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 14 ms 19308 KB contestant found the optimal answer: 933702 == 933702
7 Correct 81 ms 19436 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 22 ms 19308 KB contestant found the optimal answer: 687136 == 687136
9 Correct 14 ms 19308 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 35 ms 19324 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 35308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 35308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 34476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 35436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -