제출 #1076422

#제출 시각아이디문제언어결과실행 시간메모리
1076422YassirSalama수열 (APIO14_sequence)C++17
28 / 100
110 ms3420 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define int long long #define all(v) v.begin(),v.end() #define pii pair<int,int> #define F first #define S second template<typename T> void dbg(const T& t){ cout<<t<<endl; } template<typename T,typename... Args> void dbg(const T& t,const Args&... args){ cout<<t<<" , "; dbg(args...); } #define dbg(...) cout<<"("<<#__VA_ARGS__<<") : ";dbg(__VA_ARGS__); const int maxn=1000+10; int n,k; int pref[maxn]; int v[maxn]; int sum(int l,int r){ if(l>r) return 0LL; if(l==0) return pref[r]; return pref[r]-pref[l-1]; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>v[i]; } for(int i=1;i<=n;i++){ pref[i]=v[i]; if(i) pref[i]+=pref[i-1]; } int dp[n+1][k+1]; for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j]=-1e18; dp[0][0]=0; int ans=0; int dp2[n+1][k+1]; memset(dp2,0,sizeof(dp2)); for(int i=1;i<=n;i++){ for(int j=i;j>=1;j--){ for(int t=k;t>=1;t--){ int x=dp[j-1][t-1]+sum(j,i)*sum(i+1,n); if(dp[i][t]<x){ dp[i][t]=x; dp2[i][t]=j; ans=max(ans,dp[i][t]); } } } } cout<<ans<<"\n"; vector<int> a; int t=k; for(int i=n;i>=1;i--){ if(dp[i][t]==ans){ a.pb(i); ans=dp[dp2[i][t]-1][t-1]; t--; // break; } } reverse(all(a)); for(auto x:a){ cout<<x<<" "; } cout<<"\n"; return 0; }
#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...