Submission #517062

# Submission time Handle Problem Language Result Execution time Memory
517062 2022-01-22T13:11:15 Z Gurban Split the sequence (APIO14_sequence) C++17
0 / 100
17 ms 6240 KB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 203;
const int maxn=1e5+3;
int n,k;
ll p[maxn];
pair<ll,int> dp[N][maxn];

struct line {
    ll m, c;
    int idx;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		int x; cin >> x;
		p[i] = x + p[i - 1];
	}

	for(int i = 1;i <= k;i++){
		deque<line>dq;
		dq.push_front({p[i],dp[i-1][i].first - p[i] * p[i],i});
		for(int j = i + 1;j <= n;j++){
			while(dq.size() >= 2 and dq[0].eval(p[j]) <= dq[1].eval(p[j])) dq.pop_front();
			dp[i][j].first = dq[0].eval(p[j]);
			dp[i][j].second = dq[0].idx;
			line cur = {p[j],dp[i - 1][j].first - p[j] * p[j],j};
			while(dq.size() >= 2 and cur.intersectX(dq.back()) >= dq.back().intersectX(dq[(int)dq.size()-2])) dq.pop_back();
			dq.push_back(cur);
		}
	}
	cout<<dp[k][n].first<<'\n';
	int idx = dp[k][n].second;
	for(int i = k-1;i >= 0;i--){
		cout<<idx<<' ';
		idx = dp[i][idx].second;
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB contestant found the optimal answer: 108 == 108
2 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 316 KB contestant didn't find the optimal answer: 1093924 < 1093956
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 332 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 2 ms 1996 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 136631827923 < 1499437552673
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 21503354 < 21503404
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 840 KB contestant didn't find the optimal answer: 1818678300 < 1818678304
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6240 KB contestant didn't find the optimal answer: 19795776617 < 19795776960
2 Halted 0 ms 0 KB -