oj.uz

Submission #312040

# Submission time Handle Problem Language Result Execution time Memory
312040 2020-10-12T08:12:01 Z vuhoanggiap Split the sequence (APIO14_sequence) C++17
0 / 100
 42 ms 9064 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
using namespace std; 
typedef pair<int, int> ii; 
typedef pair<ii, int> pii;  // Line + id 

int n, k; 
int a[100005], pre[100005]; 

int dp[205][100005]; 
int trace[205][100005]; 

struct Convex_hull_linear {
	vector<pii> v; 
	int ptr = 0; 
	
	void init() {
		v.clear(); 
		ptr = 0; 
	}
	
	// y = kx + m; 
	double isect(ii x, ii y) {
		int k1 = x.fi, k2 = y.fi; 
		int m1 = x.se, m2 = y.se; 
		return (m2 - m1) * 1.0 / (k1 - k2) * 1.0; 
	}
	
	bool bad(ii a, ii b, ii c) {
		return isect(a, b) >= isect(b, c); 
	}
	
	void add(ii x, int id) {
		while(v.size() >= 2 and bad(v[v.size() - 2].fi, v[v.size() - 1].fi, x)) v.pop_back(); 
		v.pb({x, id}); 
	}
	
	int eval(ii Line, int x) {
		return Line.fi * x + Line.se; 
	}
	
	ii query(int x) {
		if(ptr > (int)v.size() - 1) {
			ptr = (int)v.size() - 1; 
		} // empty ? 
		while(ptr < (int)v.size() - 1 and eval(v[ptr].fi, x) < eval(v[ptr + 1].fi, x)) {
			ptr++; 
		}
		return {eval(v[ptr].fi, x), v[ptr].se};
	}
} Cvh;

signed main() {
	cin >> n >> k; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; 
		pre[i] = pre[i - 1] + a[i]; 
	}
	for(int j = 2; j <= k + 1; j++) {
		Cvh.init(); 
		Cvh.add({0, 0}, 0);
		for(int i = 1; i <= n; i++) {
			ii new_dp = Cvh.query(pre[i]); 
			Cvh.add({pre[i], dp[j - 1][i] - pre[i] * pre[i]}, i); 
			dp[j][i] = new_dp.fi;
			trace[j][i] = new_dp.se; 
		}
	}
	cout << dp[k + 1][n] << '\n'; 
	vector<int> res; 
	int trace_i = n; 
	for(int j = k + 1; j > 0; j--) {
		res.pb(trace[j][trace_i]); 
		trace_i = trace[j][trace_i]; 
	}
	reverse(res.begin(), res.end()); 
	for(auto x : res) {
		if(!x) continue; 
		cout << x << ' '; 
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 384 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 384 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

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