oj.uz

Submission #1088226

# Submission time Handle Problem Language Result Execution time Memory
1088226 2024-09-14T06:59:57 Z Nurislam Split the sequence (APIO14_sequence) C++17
0 / 100
 19 ms 12364 KB 
#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, 0));
	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;
	while(ans.ss > 0 && k > 0){
		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 0 ms 348 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 348 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 344 KB contestant found the optimal answer: 0 == 0
4 Incorrect 0 ms 348 KB contestant didn't find the optimal answer: 1542522 < 1542524
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 12364 KB contestant didn't find the optimal answer: 13199711688 < 19795776960
2 Halted 0 ms 0 KB -