Submission #490871

#	Time	Username	Problem	Language	Result	Execution time	Memory
490871		hohohaha	Split the sequence (APIO14_sequence)	C++14	100 / 100	956 ms	89436 KiB

sequence

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
//   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int inf = LLONG_MAX / 2ll;
const int maxn = 2e5 + 5; 
int n, k; 
int32_t arr[maxn]; 
int pref[maxn]; 

vi now, prv; 

struct line { 
	int32_t a; int b; int32_t id; 
	line(int a = 0, int b = 0, int id = 0) : a(a), b(b), id(id) {
	}
	int get(int x) { 
		return 1ll * a * x + b; 
	}
}; 

bool red(line x, line y, line z) { 
	return (x.b - y.b) * (z.a - y.a) >= (y.b - z.b) * (y.a - x.a); 
}

int32_t tr[maxn][205]; 

void solve() {
	cin >> n >> k; k++; 
	fori(i, 1, n) { 
		cin >> arr[i]; 
		pref[i] = arr[i] + pref[i - 1]; 
	}
	now = prv = vi(n + 1, -inf); 
	now[0] = 0; 
	fori(t, 1, k) { 
		now.swap(prv); 
		fill(all(now), -inf); 
//		now[0] = 0; 
		
//		cout << t << endl;
		
		vector<line> C; int ptr = -1; 
		fori(i, 1, n) { 
			if(prv[i - 1] > -inf) {
				line nw(pref[i - 1], prv[i - 1] - pref[i -1] * pref[i - 1], i - 1); 
				while(1) { 
					if(C.size() > 0 and (end(C) - 1)->a == nw.a and (end(C) - 1)->b < nw.b) C.ob(); 
					else if(C.size() > 1 and red(*(end(C) - 2), *(end(C) - 1), nw) ) C.ob(); 
					else break; 
				}
				ptr = min(ptr, (int)C.size() - 1); 
				C.eb(nw); 
			}
//			cout << i << endl;
			ptr = min(ptr, (int)C.size() - 1); 
			while(ptr + 1 < C.size() and (ptr == -1 or C[ptr].get(pref[i]) <= C[ptr + 1].get(pref[i]))) ++ptr; 
			if(ptr > -1) {
				now[i] = C[ptr].get(pref[i]); 
				tr[i][t] = C[ptr].id; 
			}
//			cout << i << sp << t << sp << ptr << sp << tr[i][t] << sp << now[i] << endl;
		}
	}
	cout << now[n] << endl; 
	int pos = n; 
	vi ans; 
	ford(i, k, 1) { 
		ans.eb(pos); //cout << pos << sp; 
//		cout << k << sp << pos << endl;
		pos = tr[pos][i]; 
	}
	reverse(all(ans)); 
	fori(i, 0, k - 2) cout << ans[i] << sp; 
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:117:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    while(ptr + 1 < C.size() and (ptr == -1 or C[ptr].get(pref[i]) <= C[ptr + 1].get(pref[i]))) ++ptr;
      |          ~~~~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29