제출 #34039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34039		wan2000	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1840 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+111;
const int K = 222;

int n, k, Tr[K][N];
ll A[N], S[N], F[K][N], res;

bool maxi(ll &x, ll y){
    if(x<y) x = y;
    else return 0;
    return 1;
}

void BackTrack(int x, int d){
    if(d==0) return;
    cout<<x<<' ';
    BackTrack(Tr[d][x],d-1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>A[i];
        S[i] = S[i-1]+A[i];
    }
    for(int ii = 1; ii <= k; ii++){
        for(int i = n; i >= 1; i--){
            F[ii][i] = 0;
            for(int j = i+1; j <= n; j++){
                if(maxi(F[ii][i],F[ii-1][j]+S[i]*(S[j]-S[i]))){
                    Tr[ii][i] = j;
                }
            }
        }
    }
    int s;
    for(int i = 1; i <= n; i++){
        if(maxi(res,F[k][i])){
            s = i;
        }
    }
    cout<<res<<'\n';
    BackTrack(s,k);
    return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:43:9: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int s;
         ^

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