제출 #977351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977351		hocln	수열 (APIO14_sequence)	C++17	62 / 100	689 ms	83292 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
struct Line {
	ll m, c, ind;
	Line(){m = c = 0, ind = -1;}
	Line(ll a, ll b, ll i){ m = a, c = b, ind = i;}
	ll val(ll x) {return m * x + c;}
	ld inter(Line a) {return (ld)(c - a.c) / (ld)(a.m- m);}
};
const int N = 1e5 + 15;
const int K = 202;
int pos[N][K];
ll dp[N][2], pref[N];
inline void solve_test() {
	ll n, k;
	cin >> n >> k;
	for(int i = 1, x;i <= n;i++) {
		cin >> x;
		pref[i] = pref[i-1] + x;
	}
	// k = n - 1
	// j = k - 1
	// j = j + 1
	// j = k
	// j = k 
	// j = n - 1
	// good
	// prefixs are decreasing
	// 
	for(int j = 0;j < k;j++) {
		deque<Line>d;
		// dp[i][j+1] = (pref[n-1]-pref[i]) * pref[i] + max(1 <= l < i) dp[l][j] - pref[i] * (pref[n-1]-pref[i])
		//pos[j+1][j+1] = j;
		//dp[j+1][1] = dp[j][0] + (pref[n] - pref[j+1]) * (pref[j+1] - pref[j]);
		//d.emplace_back(-pref[j+1],
		d.emplace_back(-pref[j],dp[j][0],j);
		for(int i = j+1;i < n;i++) {
			ll x = pref[n]-pref[i];
			//debug()<<imie(d.back().ind);
			while(d.size() >= 2 && d.back().val(x) <= d[(int)d.size()-2].val(x)) d.pop_back();
			pos[i][j+1] = d.back().ind;
			dp[i][1] = x * pref[i] + d.back().val(x);
			//debug()<<imie(d.size())imie(x)imie(d.front().val(x))imie(d.front().ind)imie(d.front().m)imie(d.front().c)imie(dp[i][1])imie(i)imie(x*pref[i]);
			Line res = {-pref[i],dp[i][0],i};
			while(d.size() >= 2 && res.inter(d.front()) >= d[0].inter(d[1])) d.pop_front();
			d.push_front(res);
		}
		//for(int i = 0;i < n;i++) debug()<<imie(i)imie(j)imie(dp[i][1]);
		for(int i = 0;i < n;i++) dp[i][0] = dp[i][1];
	}
	ll mx = -INF, st = -1;
	for(int i = n - 1;i;i--) if(chmax(mx, dp[i][0])) st = i;
	assert(~st);
	cout << mx << '\n';
	for(int i = 0;i < k;i++) {
		cout << st << ' ';
		st = pos[st][k-i];
	}
	
}
 
int main()
{
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    //freopen("convention2.in", "r", stdin);
    //freopen("convention2.out", "w", stdout);
	//cout << "Case #" << tc << ": " << ans << '\n';
	//cout << fixed << setprecision(7);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
		++tc;
        solve_test();
    }
}

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