제출 #1293744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293744		AbdullahIshfaq	수열 (APIO14_sequence)	C++20	100 / 100	301 ms	81356 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD 998244353
const int N = 100005, lg = 205;
int q[N], p[lg][N];
ll a[N], tmp1[N], tmp2[N];
void path(int k, int n)
{
    if (k < 0)
        return;
    path(k - 1, p[k][n]);
    cout << n << ' ';
}
void solve()
{
	int n, k, f, r;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
        tmp1[i] = -a[i] * a[i];
    }
    for (int i = 1; i <= k; i++)
    {
        f = 1;
        r = 1;
        q[1] = i;
        for (int j = i + 1; j <= n; j++)
        {
            while (f < r and a[q[f]] * a[j] + tmp1[q[f]] <= a[q[f + 1]] * a[j] + tmp1[q[f + 1]])
            {
                f++;
            }
            tmp2[j] = a[q[f]] * a[j] + tmp1[q[f]] - a[j] * a[j], p[i][j] = q[f];
            while (f < r and (tmp1[q[r]] - tmp1[q[r - 1]]) * (a[q[r - 1]] - a[j]) >= (tmp1[j] - tmp1[q[r - 1]]) * (a[q[r - 1]] - a[q[r]]))
            {
                r--;
            }
            r++;
            q[r] = j;
        }
        for (int j = i + 1; j <= n; j++)
        {
            tmp1[j] = tmp2[j];
        }
    }
    cout << tmp1[n] + a[n] * a[n] << '\n';
    path(k - 1, p[k][n]);
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	// cout << fixed << setprecision(12);
	for (int i = 1; i <= t; i++)
	{
		solve();
	}
}

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