제출 #1290183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290183		blackscreen1	수열 (APIO14_sequence)	C++20	71 / 100	394 ms	162048 KiB

sequence

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
ll n, m, a[100005];
ll dp[3][100005], cont[205][100005];
deque<pll> dq;
deque<ll> prv;
void insert(pll line) {
	while (dq.size()) {
		if (dq.front().first == line.first && dq.front().second <= line.second) {dq.pop_front(); prv.pop_front();}
		else if (dq.size() >= 2 && (dq[1].second - line.second)*(line.first - dq[0].first) >= (dq[0].second - line.second)*(line.first - dq[1].first)) {dq.pop_front(); prv.pop_front();}
		else break;
	}
	dq.push_front(line);
}
ll qu(ll x) {
	if (!dq.size()) return 0;
	while (dq.size() >= 2) {
		pll tmp = dq.back();
		dq.pop_back();
		if (dq.back().first * x + dq.back().second < tmp.first * x + tmp.second) {dq.push_back(tmp); break;}
		prv.pop_back();
	}
	return dq.back().first * x + dq.back().second;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	iloop(0, n) cin >> a[i];
	// gna do without cht first
	ll pf[n+1];
	pf[0] = 0;
	iloop(0, n) pf[i+1] = pf[i] + a[i];
	memset(dp, 0, sizeof(dp));
	iloop(1, m+1) {
		jloop(1, n+1) {
			//cout << "dp " << i << " " << j << ":\n";
			//cout << "querying " << pf[j] << "\n";
			dp[1][j] = qu(pf[j]);
			//cout << "res " << dp[i][j] << "\n";
			cont[i][j] = (prv.size() ? prv.back() : -1);
			insert({pf[j], dp[0][j] - pf[j] * pf[j]});
			//cout << "insert " << pf[j] << " " << dp[i-1][j] - pf[j] * pf[j] << " as " << j << "\n";
			prv.push_front(j);
		}
		dq.clear();
		prv.clear();
		swap(dp[0], dp[1]);
	}
	cout << dp[0][n] << "\n";
	ll ct = n;
	iloop(m, 0) {
		ct = cont[i][ct];
		cout << ct << " ";
	}
	//cout << "\n";
	//iloop(1, m+1) {jloop(1, n+1) {cout << cont[i][j] << " ";} cout << "\n";}
}

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