Submission #1338609

#TimeUsernameProblemLanguageResultExecution timeMemory
1338609vtnooRastuci (COCI25_rastuci)C++20
27 / 110
30 ms2500 KiB
#include <bits/stdc++.h>
#define V vector
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; 

template<typename T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int N=500;
const ll I=1e18;
ll dp[N][N];

void chmin(ll &a,ll b){
	a=min(a,b);
}

int main(){
	int n;cin>>n;
	V<ll>v(n);
	L(i,0,n-1)cin>>v[i];
	if(n==1){
		cout<<0<<endl;
		cout<<v[0]<<endl;
		return 0;
	}
	L(i,0,n-1)L(j,0,n-1)dp[i][j]=I;
	dp[0][0]=0; 
	L(i,1,n-1){
		ll f=0;
		R(j,i,0){
			f+=v[j];
			if(j==0)chmin(dp[i][j],i-j);
			else{
				ll s=0;
				R(k,j-1,0){
					s+=v[k];
					if(f>=s)chmin(dp[i][j],dp[j-1][k]+(i-j));
				}
			}
		}
	}
	ll ans=I;
	L(i,0,n-1)chmin(ans,dp[n-1][i]); 
	cout<<n-ans<<endl;
	L(i,0,n-ans-1)cout<<1<<" ";
	cout<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...