제출 #989409

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

sequence

#include "bits/stdc++.h"
using namespace std;
 
#ifdef N_N_C
#include "debug.h"
#else
#define cebug(...) "Arya"
#endif
 
#define ll long long
 
const int N=1e5+5;
const int mod=1e9+7;
 
int n,k,a[N],op[205][N];
ll dp[205][N],p[N];
void dnc(int j, int l, int r, int optl, int optr){
	if(l>r) return;
	int mid=(l+r)>>1;
	pair <ll,int> opt={0,0};
	for(int x=min(mid,optr); x>=optl; x--) opt=max(opt,{dp[j-1][x-1]+(p[mid]-p[x-1])*(p[n]-p[mid]),x});
	if(j==2 and mid==7) cebug(opt);
	dp[j][mid]=opt.first;
	op[j][mid]=opt.second;
	dnc(j,l,mid-1,optl,opt.second);
	dnc(j,mid+1,r,opt.second,optr);
}
vector <int> trc;
void trace(int d, int j){
	if(!d) return;
	trc.push_back(j);
	trace(d-1,op[d][j]-1);
}
void sol(){
	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>a[i],p[i]=p[i-1]+a[i];
	for(int j=1; j<=k; j++) dnc(j,j,n-1,1,n);
	// for(int j=1; j<=k; j++){
		// for(int i=1; i<j; i++) cout<<"   ";
		// for(int i=j; i<n; i++) cout<<dp[j][i]<<" ";
		// cout<<"\n";
	// }
	ll ans=0;
	for(int i=1; i<n; i++) ans=max(ans,dp[k][i]);
	cout<<ans<<"\n";
	int pos=0;
	for(int i=1; i<n; i++) if(dp[k][i]==ans) pos=i;
	trace(k,pos);
	reverse(trc.begin(),trc.end());
	for(auto x:trc) cout<<x<<" ";
}
signed main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    int tt=1;
    //cin>>tt; 
    while(tt--){
    	sol();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

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

sequence.cpp: In function 'void dnc(int, int, int, int, int)':
sequence.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define cebug(...) "Arya"
      |                    ^~~~~~
sequence.cpp:22:22: note: in expansion of macro 'cebug'
   22 |  if(j==2 and mid==7) cebug(opt);
      |                      ^~~~~

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