oj.uz

답안 #304410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304410 2020-09-21T09:44:35 Z vipghn2003 수열 (APIO14_sequence) C++14
0 / 100
 906 ms 18168 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int K=205;
int n,k,a[N],s[N],dp[K][N],opt[K][N];

void calc(int lev,int l,int r,int L,int R)
{
    if(l>r) return ;
    int mid=(l+r)/2;
    dp[lev][mid]=-1e9;
    for(int i=L;i<=min(mid-1,R);i++)
    {
        if(dp[lev][mid]<dp[lev-1][i]+(s[mid]-s[i])*(s[n]-s[mid]))
        {
            dp[lev][mid]=dp[lev-1][i]+(s[mid]-s[i])*(s[n]-s[mid]);
            opt[lev][mid]=i;
        }
    }
    //cout<<lev<<' '<<mid<<' '<<dp[lev][mid]<<'\n';
    calc(lev,l,mid-1,L,opt[lev][mid]);
    calc(lev,mid+1,r,opt[lev][mid],R);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    dp[1][0]=-1e9;
    for(int i=1;i<=n;i++)
    {
        dp[1][i]=s[i]*(s[n]-s[i]);
        opt[1][i]=i;
    }
    for(int lev=2;lev<=k;lev++) calc(lev,1,n,0,n-1);
    int res=-1e9,cur;
    for(int i=1;i<=n;i++)
    {
        if(res<dp[k][i])
        {
            res=dp[k][i];
            cur=i;
        }
    }
    cout<<res<<'\n';
    while(k)
    {
        cout<<cur<<' ';
        cur=opt[k][cur];
        k--;
    }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:57:12: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         cur=opt[k][cur];
      |         ~~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 384 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Incorrect 1 ms 384 KB Integer 0 violates the range [1, 9]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 384 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 1 ms 896 KB Integer 0 violates the range [1, 49]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 384 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 3 ms 2560 KB Integer 0 violates the range [1, 199]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 384 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 12 ms 3840 KB Integer 0 violates the range [1, 999]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 2 ms 768 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Incorrect 906 ms 18168 KB Integer 0 violates the range [1, 9999]
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 134 ms 3448 KB Integer 0 violates the range [1, 99999]
2 Halted 0 ms 0 KB -