제출 #919528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919528		vjudge1	수열 (APIO14_sequence)	C++17	100 / 100	1072 ms	82400 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(v) (v).begin(),(v).end()
const int maxN=1e5+5;
const ll Inf=1e18+5;
ll Dp[2][maxN];
int Trace[205][maxN],Ps[maxN],n;

ll Cost(int l,int r)
{
    return 1ll*(Ps[n]-Ps[r])*(Ps[r]-Ps[l-1]);
}

void Calc_dp(int i,int l,int r,int u,int v)
{
    if (l>r) return;
    int mid=l+r>>1;
    for (int j=u;j<=min(v,mid);++j) {
        ll Tmp=Dp[i&1^1][j-1]+Cost(j,mid);
        if (Tmp>Dp[i&1][mid]) {
            Dp[i&1][mid]=Tmp;
            Trace[i][mid]=j;
        }
    }
    if (!Trace[i][mid]) return;
    Calc_dp(i,l,mid-1,u,Trace[i][mid]);
    Calc_dp(i,mid+1,r,Trace[i][mid],v);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    #define taskname "sequence"
    if (fopen(taskname".in","r")) {
        freopen(taskname".in","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    int k,a;
    cin>>n>>k;
    for (int i=1;i<=n;++i) {
        cin>>a;
        Ps[i]=Ps[i-1]+a;
        Dp[0][i]=-Inf;
    }
    for (int j=1;j<=k;++j) {
        for (int i=0;i<=n;++i) Dp[j&1][i]=-Inf;
        Calc_dp(j,1,n-1,1,n-1);
    }
    ll Res=-Inf,Pos=0;
    for (int i=1;i<=n;++i)
        if (Dp[k&1][i]>Res) {
            Res=Dp[k&1][i];
            Pos=i;
        }
    cout<<Res<<'\n';
    vector<int> PosList;
    while (Pos) {
        PosList.push_back(Pos);
        Pos=Trace[k--][Pos]-1;
    }
    reverse(all(PosList));
    for (int i:PosList) cout<<i<<" ";
}
/*
7 3
4 1 3 4 0 2 3
*/

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

sequence.cpp: In function 'void Calc_dp(int, int, int, int, int)':
sequence.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid=l+r>>1;
      |             ~^~
sequence.cpp:21:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   21 |         ll Tmp=Dp[i&1^1][j-1]+Cost(j,mid);
      |                   ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(taskname".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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