oj.uz

Submission #107062

# Submission time Handle Problem Language Result Execution time Memory
107062 2019-04-21T16:11:38 Z figter001 Split the sequence (APIO14_sequence) C++17
0 / 100
 89 ms 1656 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 2e5;

int pre[nax];

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> a(n),c;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++){
		pre[i] = a[i];
		if(i)pre[i] += pre[i-1];
	}
	ll ans = 0;
	vector<int> cur;
	cur.push_back(n);
	for(int i=0;i<k;i++){
		ll mx = 0;
		int id = 0,at = 0,q = 0,b = 0;
		int lf = 0,ri = 0;
		for(int j=0;j<n-1;j++){
			if(q == cur[id] - 1){
				q = 0;
				id++;
			}else{
				ll pf = 0;
				if(j-q-1 >= 0)pf = pre[j-q-1];
				ll points = (pre[j] - pf) * (pre[j-q+cur[id]-1] - pre[j]);
				if(points > mx){
					mx = points;
					at = j;
					b = id;
					lf = cur[id] - q - 1;
					ri = cur[id] - lf;
				}
				q++;
			}
		}
		ans += mx;
		cur.erase(cur.begin() + b);
		cur.insert(cur.begin() + b,lf);
		cur.insert(cur.begin() + b,ri);
		c.push_back(at);
	}
	cout << ans << endl;
	// sort(c.begin(),c.end());
	for(int i : c)
		cout << i+1 << ' ';
	printf("\n");
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB contestant found the optimal answer: 108 == 108
2 Incorrect 3 ms 384 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 3 ms 384 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 3 ms 384 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 2 ms 256 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Incorrect 2 ms 256 KB contestant didn't find the optimal answer: 1019625813 < 1019625819
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB contestant didn't find the optimal answer: 21419072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1124 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 24 ms 1280 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Incorrect 89 ms 1656 KB contestant didn't find the optimal answer: 497009314607795353 < 497313449256899208
4 Halted 0 ms 0 KB -