이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 10000+5 , K = 200+5 , INF = 1e18 , MOD = 1e9+7;
ll n,k;
ll dp[N][N],opt[N][N];
vector<ll> presum(N);
ll go(ll i , ll j){
if(j > k+1) return -INF;
if(i == n+1){
if(j < k+1) return -INF;
return 0;
}
if(dp[i][j] != -1) return dp[i][j];
ll ans = -INF,ind;
for(ll k = i; k <= n; k++){
ll cur = go(k+1,j+1)+(presum[k]-presum[i-1])*(presum[n]-presum[k]);
if(cur > ans){
ans = cur;
ind = k+1;
}
}
opt[i][j] = ind;
return dp[i][j] = ans;
}
void solve(){
cin >> n >> k;
vector<ll> a(n+5);
for(ll i = 1; i <= n; i++) cin >> a[i];
for(ll i = 1; i <= n; i++) presum[i] = presum[i-1]+a[i];
memset(dp,-1,sizeof dp);
cout << go(1,0) << "\n";
ll curi = 1 , curj = 0;
while(true){
curi = opt[curi][curj];
curj++;
if(curi == n+1) break;
cout << curi-1 << " ";
}
}
int main(){
fast;
ll tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'long long int go(long long int, long long int)':
sequence.cpp:31:12: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
31 | opt[i][j] = ind;
| ~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |