제출 #73572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73572		Vardanyan	수열 (APIO14_sequence)	C++14	71 / 100	2039 ms	33096 KiB

sequence

#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 100000+7;
int a[N];
long long pref[N];
//int suf[N];
pair<long long,int> dp[208][N];
int par[208][N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(int i = 1;i<=n;i++) pref[i] = pref[i-1]+a[i];
//    for(int i = n;i>=1;i--) suf[i] = suf[i+1]+a[i];
    for(int kk = 1;kk<=k;kk++){
        for(int i = kk+1;i<=n;i++){
            int st = max(dp[kk][i-1].second,kk);
            st = max(st,dp[kk-1][i].second);
            int fin = st+20;
            if(N<=10000) fin = i;
            for(int j = st;j<i;j++){
                if(dp[kk-1][j].first+(pref[i]-pref[j])*pref[j]>=dp[kk][i].first){
                    dp[kk][i].first = dp[kk-1][j].first+(pref[i]-pref[j])*pref[j];
                    dp[kk][i].second = j;
                }
              //  else break;
            }
        }
    }
    cout<<dp[k][n].first<<endl;
    int kk = k;
    int nn = n;
    while(kk>0){
        cout<<dp[kk][nn].second<<" ";
        nn = dp[kk][nn].second;
        kk--;
    }
    cout<<endl;
    return 0;
}

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

sequence.cpp: In function 'int main()':
sequence.cpp:21:17: warning: variable 'fin' set but not used [-Wunused-but-set-variable]
             int fin = st+20;
                 ^~~
sequence.cpp:14:34: 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("%d",&a[i]);
                             ~~~~~^~~~~~~~~~~~

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