# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
745031 | sudheerays123 | 수열 (APIO14_sequence) | C++17 | 9 ms | 2516 KiB |
이 제출은 이전 버전의 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 = 10+5 , K = 200+5 , INF = 1e18 , MOD = 1e9+7;
ll n,k;
ll dp[N][K],opt[N][K];
vector<ll> presum(N);
void dnc(ll l , ll r , ll j , ll optl , ll optr){
if(l > r) return;
ll mid = (l+r)/2;
if(dp[mid][j] != -1) return;
ll ind, ans = -INF;
for(ll i = optl; i <= min(optr,mid); i++){
ll cost = dp[i-1][j-1] + presum[i-1]*(presum[mid]-presum[i-1]);
if(cost > ans){
ans = cost;
ind = i;
}
}
dp[mid][j] = ans;
opt[mid][j] = ind;
dnc(l,mid-1,j,optl,ind);
dnc(mid+1,r,j,ind,optr);
}
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);
for(ll i = 1; i <= n+2; i++) dp[i][0] = -INF;
dp[0][0] = 0;
for(ll i = 1; i <= k+1; i++) dnc(1,n,i,1,n);
cout << dp[n][k+1] << "\n";
ll curi = opt[n][k+1] , curj = k;
vector<ll> path;
while(true){
curi = opt[curi][curj];
curj--;
if(curi == 0) break;
path.push_back(curi);
}
reverse(path.begin(),path.end());
for(auto u : path) cout << u << " ";
}
int main(){
fast;
ll tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |