제출 #744949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744949		zeta7532	수열 (APIO14_sequence)	C++17	11 / 100	558 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)
 
ll ans[50][50][50][2][3];
set<ll> s;

void dfs(ll x,ll y,ll z){
    ll x0=ans[x][y][z][0][0];
    ll y0=ans[x][y][z][0][1];
    ll z0=ans[x][y][z][0][2];
    ll x1=ans[x][y][z][1][0];
    ll y1=ans[x][y][z][1][1];
    ll z1=ans[x][y][z][1][2];
    s.insert(x1);
    if(z0) dfs(x0,y0,z0);
    if(z1) dfs(x1,y1,z1);
}
 
int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    vector<ll> sum(N+1);
    sum[0]=0;
    rep(i,N) sum[i+1]=sum[i]+A[i];
    vector<vector<vector<ll>>> dp(N,vector<vector<ll>>(N,vector<ll>(K+1,0)));
    rep(k,K){
        rep(i,N-k){
            for(ll j=i+k+1;j<N;j++){
                for(ll x=i;x<j;x++){
                    for(ll y=0;y<=k;y++){
                        ll z=dp[i][x][y]+dp[x+1][j][k-y]+(sum[x+1]-sum[i])*(sum[j+1]-sum[x+1]);
                        if(dp[i][j][k+1]<z){
                            dp[i][j][k+1]=z;
                            ans[i][j][k+1][0][0]=i;
                            ans[i][j][k+1][0][1]=x;
                            ans[i][j][k+1][0][2]=y;
                            ans[i][j][k+1][1][0]=x+1;
                            ans[i][j][k+1][1][1]=j;
                            ans[i][j][k+1][1][2]=k-y;
                        }
                    }    
                }
            }
        }
    }
    cout << dp[0][N-1][K] << endl;
    dfs(0,N-1,K);
    auto it=s.begin();
    while(it!=s.end()){
        cout << *it << " ";
        it++;
    }
    cout << endl;
    return 0;
}

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