oj.uz

Submission #310139

# Submission time Handle Problem Language Result Execution time Memory
310139 2020-10-05T23:41:30 Z sofapuden Split the sequence (APIO14_sequence) C++14
0 / 100
 77 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> v(100005);
vector<vector<ll>> dp(2,vector<ll>(100005)), L(100005,vector<ll>(205));
ll k;

void find(ll l, ll r, ll lb, ll rb, ll Z){
	if(l > r)return;
	ll mid = (l+r)>>1;
	
	ll pos = lb, ma = -1;
	for(int i = lb; i < min(mid,rb+1); ++i){
		if(ma < dp[0][i]+(v[mid]-v[i])*v[i]){
			ma = dp[0][i]+(v[mid]-v[i])*v[i];
			pos = i;
		}
	}
	dp[1][mid] = ma;
	L[mid][Z] = pos;
	find(l,mid-1,lb,pos,Z);
	find(mid+1,r,pos,rb,Z);
}
	

int main(){
	int n; cin >> n >> k;
	for(int i = 0; i++ < n;){
		cin >> v[i];
	}
	if(n == 2){
		cout << v[1]*v[2] << "\n";
		cout << 1 << "\n";
	}
	for(int i = 0; i++ < n;){
		v[i]+=v[i-1];
	}
	for(int i = 1; i<=k; ++i){
		find(1,n,1,n,i);
		for(int j = 1; j <= n; ++j)dp[0][j] = dp[1][j];
	}
	ll ans = 0; ll ind = 0;
	for(int i = 1; i <= n; ++i){
		if(ans < dp[0][i]){
			ind = i;
			ans = dp[0][i];
		}
	}
	cout << ans << "\n";
	
	while(k--){
		cout << L[ind][k]+1 << " ";
		ind = L[ind][k];
	}
	cout << "\n";
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 131076 KB Execution killed with signal 9 (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 70 ms 131072 KB Execution killed with signal 9 (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 75 ms 131076 KB Execution killed with signal 9 (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 73 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -