Submission #1088242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088242	2024-09-14T07:09:58 Z	Nurislam	Split the sequence (APIO14_sequence)	C++17	0 / 100	21 ms	12616 KB

sequence

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
const int N = 1e6+50, inf = 1e17;
//int mod = 998244353
//int mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct line{
	int m, c, i;
	
	line(int _m,int _c, int _i) : m(_m), c(_c), i(_i){
	};
	
	int calc(int x){
		return m * x + c;
	};
	
	double xnt(line & other){
		return (long double)(c - other.c)/(m - other.m);
	};
};

void solve(){
	int n, k;
	cin >> n >> k;
	vector<int> v(n+1);
	for(int i = 1; i<= n; i++){cin >> v[i];v[i] += v[i-1];}
	
	vector<vector<int>> dp(2, vector<int> (n+2));
	vector<vector<int>> from(n+2, vector<int> (k+2));
	
	for(int j = 1; j <= k; j++){
		//cout << 1 << '\n';
		deque<line> dq;
		dq.pb({0,0,0});
		for(int i = 1; i <= n; i++){
			int ps = v[n] - v[i];
			while(dq.size() > 1 && dq.back().calc(ps) <= dq[dq.size()-2].calc(ps))
				dq.pop_back();
				
			dp[1][i] = dq.back().calc(ps) + v[i] * ps;
			from[i][j] = dq.back().i;
			
			line nw = {-v[i], dp[0][i], i};
			while(dq.size() > 1 && nw.xnt(dq[0]) > dq[0].xnt(dq[1]))
				dq.pop_front();
			
			dq.push_front(nw);
		}
		dp[0] = dp[1];
	}
	pair<int,int> ans = {-1, 0};
	for(int i = 1; i < n; i++){
		ans = max(ans, {dp[0][i], i});
	}
	cout << ans.ff << '\n';
	vector<int> res;
	for(; k > 0; k--){
		res.pb(ans.ss);
		ans.ss = from[ans.ss][k];
	}	
	reverse(all(res));
	
	
	for(int i:res)cout << i << ' ';
	cout << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	contestant found the optimal answer: 108 == 108
2	Correct	0 ms	348 KB	contestant found the optimal answer: 999 == 999
3	Correct	0 ms	348 KB	contestant found the optimal answer: 0 == 0
4	Correct	1 ms	348 KB	contestant found the optimal answer: 1542524 == 1542524
5	Correct	0 ms	348 KB	contestant found the optimal answer: 4500000000 == 4500000000
6	Correct	1 ms	348 KB	contestant found the optimal answer: 1 == 1
7	Correct	0 ms	348 KB	contestant found the optimal answer: 1 == 1
8	Correct	0 ms	348 KB	contestant found the optimal answer: 1 == 1
9	Correct	1 ms	344 KB	contestant found the optimal answer: 100400096 == 100400096
10	Correct	1 ms	344 KB	contestant found the optimal answer: 900320000 == 900320000
11	Incorrect	1 ms	348 KB	contestant didn't find the optimal answer: 3498210227 < 3698080248
12	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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