제출 #37901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37901		MatheusLealV	수열 (APIO14_sequence)	C++14	0 / 100	79 ms	86100 KiB

sequence

#include <bits/stdc++.h>
#define f first
#define s second
#define N 100005
#define K 202
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
 
int r, e, n, k, prox[N][K], ID[N];

bool block[N];

ll A[N],B[N], dp[3][N], sum[N];

vector<pair<pii, int> > line;

void addline(pair<pii, int> l)
{
    A[e] = l.f.f, B[e] = l.f.s, ID[e] = l.s;

    while(r + 1 < e && (B[e-1] - B[e-2]) * (A[e] - A[e-1]) <= (A[e-2] - A[e-1])* (B[e-1] - B[e])) A[e-1] = A[e], B[e-1] = B[e], ID[e-1] = ID[e], e--;

    e++;
}

pii query(ll x)
{
    while(r + 1 < e && B[r + 1] - B[r] >= x * (A[r] - A[r + 1])) r++;

    return pii(A[r]*x + B[r],ID[r]);
}
 
int32_t main()
{
    scanf("%d %d",&n,&k);

    for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];

    for(int i = 0; i <= n; i++) dp[0][i] = 0;

    int A = 0, B = 1;
     
    for(int q = 0; q <= k; q++)
    {
        r = e = 0;

        addline(make_pair(pii(0, 0), 0));

        for (int i = 1; i <= n; i++)
        {
            pii x = query(sum[i]);

            prox[i][q] = x.s;

            dp[A][i] = x.f + sum[i]*(sum[n] - sum[i]);

            addline(make_pair(pii(sum[i], dp[B][i] - sum[n]*sum[i]), i));
        }

        swap(A, B);
    }

    printf("%lld\n",dp[k%2][n]);

    int ini = n, q = k, qtd = 0;

    while(true)
    {
      if(!prox[ini][q]) break;
 
      qtd ++;
 
      block[prox[ini][q]] = 1;
 
      printf("%d ", prox[ini][q]);
 
      ini = prox[ini][q] + 1;
    
      q --;
    }
 
    int extra = k - qtd;
 
    for(int i = 1, cnt = 0; i <= n && cnt < extra; i++)
    {
      if(!block[i]) printf("%d ", i), cnt ++;
    }
 
    cout<<"\n";

}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int32_t main()':
sequence.cpp:36:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
                         ^
sequence.cpp:38:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
                                                                             ^

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