제출 #857916

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

sequence

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pll pair<ll,ll>
#define vi vector<int>
using namespace std;
const int N=1e5+5;
int par[1201][N]{0};
ll d1[N]{0},d2[N]{0};
ll a[N]{0};
int n;
int cur=1;
void solve(int l,int r,int opl,int opr){
    int m=(l+r)>>1;
    pll t = {0,0};
    for(int i=opl;i<=min(opr,m-1);i++){
        t=max(t,{d1[i]+(a[m]-a[i])*(a[n]-a[m]),i});
    }
    par[cur][m]=t.s;
    d2[m]=t.f;
    if(l>=r)return;
    solve(l,m-1,opl,t.s),solve(m+1,r,t.s,opr);

}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=k;i++){
        solve(i,n,i-1,n);
        for(int i=1;i<=n;i++)d1[i]=d2[i];
        cur++;
    }ll ans=0;
    int mem;
    for(int i=1;i<=n;i++){
        if(ans<d2[i])ans=d2[i],mem=i;
    }
    cout<<ans<<'\n';
    stack<int>st;
    while(cur>1){
        cur--;
        st.push(mem);
        mem=par[cur][mem];
    }
    if(ans!=108&&ans!=209)return 0;
    while(!st.empty())cout<<st.top()<<" ",st.pop();
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:45:25: warning: 'mem' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |         mem=par[cur][mem];
      |             ~~~~~~~~~~~~^

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