Submission #737837

#	Time	Username	Problem	Language	Result	Execution time	Memory
737837		amirhoseinfar1385	Split the sequence (APIO14_sequence)	C++17	Compilation error	0 ms	0 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
vector<vector<long long>>dp;
vector<vector<int>>dpa;
vector<long long>ps,suf;
int n,k;
 
void solve(int l,int r,int tl,int tr,int fj){
	//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<fj<<endl;
	if(l>r||tl>tr){
		return ;
	}
	if(tl==tr){
		for(int i=l;i<=r;i++){
			dpa[i][fj]=tl;
		}
		return ;
	}
	int mid=(l+r)>>1;
	for(int i=tl;i<=min(tr,mid-1);i++){
		long long fake=dp[i][fj-1]+(ps[mid]-ps[i])*suf[mid+1];
		if(fake>dp[mid][fj]){
			dp[mid][fj]=fake;
			dpa[mid][fj]=i;
		}
	}
	solve(l,mid-1,tl,dpa[mid][fj],fj);
	solve(mid+1,r,dpa[mid][fj],tr,fj);
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	vector<long long>all(n+1);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	dp.resize(n+3,vector<long long>(k+5));
	dpa.resize(n+3,vector<long long>(k+5));
	ps.resize(n+3);
	suf.resize(n+3);
	for(int i=1;i<=n;i++){
		ps[i]=ps[i-1]+all[i];
	}
	for(int i=n;i>=1;i--){
		suf[i]=all[i]+suf[i+1];
	}
	for(int i=1;i<=n;i++){
		dp[i][1]=ps[i]*suf[i+1];
		dpa[i][1]=-1;
	}
	for(int j=2;j<=k;j++){
		solve(j,n,1,n,j);
		for(int i=1;i<j;i++){
			dp[i][j]=dp[i][j-1];
			dpa[i][j]=dpa[i][j-1];
		}
		for(int i=j;i<=n;i++){
			dp[i][j]=dp[dpa[i][j]][j-1]+(ps[i]-ps[dpa[i][j]])*suf[i+1];
		}
	}
	long long maxa=-1,w=0;
	for(int i=1;i<n;i++){
		if(dp[i][k]>maxa){
			w=i;
			maxa=dp[i][k];
		}	
	}
	cout<<maxa<<"\n";
	int now=k;
	vector<int>res;
	vector<int>vis(n+3);
	while(now>0&&w>0){
		//cout<<now<<" "<<w<<endl;
		res.push_back(w);
		vis[w]=1;
		w=dpa[w][now];
		now--;
	}
	reverse(res.begin(),res.end());
	for(int i=1;i<n;i++){
		if(now>0&&vis[i]==0){
			now--;
			res.push_back(i);
		}
	}
	for(auto x:res){
		cout<<x<<" ";
	}
	cout<<endl;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:39: error: no matching function for call to 'std::vector<std::vector<int> >::resize(int, std::vector<long long int>)'
   41 |  dpa.resize(n+3,vector<long long>(k+5));
      |                                       ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
  937 |       resize(size_type __new_size)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:937:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
  957 |       resize(size_type __new_size, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:54: note:   no known conversion for argument 2 from 'std::vector<long long int>' to 'const value_type&' {aka 'const std::vector<int>&'}
  957 |       resize(size_type __new_size, const value_type& __x)
      |                                    ~~~~~~~~~~~~~~~~~~^~~