QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#775533 | #9475. Pangu and Stones | surenjamts# | WA | 0ms | 3608kb | C++20 | 1.5kb | 2024-11-23 16:10:06 | 2024-11-23 16:10:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,l,r;
while(cin>>n>>l>>r){
vector<vector<vector<int>>> dp(n+5,vector<vector<int>> (n+5, vector<int> (n+5,1e18)));
vector<int> a(n+1);
vector<int> pref(n+1);
for(int i=1; i<=n; i++){
cin>>a[i];
pref[i]=pref[i-1]+a[i];
}
for(int i=1; i<=n; i++){
dp[i][i][1]=0;
}
for(int i=2; i<=n; i++){
for(int j=1; j<=n; j++){
int lo=j, hi=lo+i-1;
if(hi>n) continue;
dp[lo][hi][i]=0;
for(int q=2; q<=i; q++){
for(int k=lo; k<hi; k++){
// for(int q=2; q<i; q++){
if(k+1<=hi)dp[lo][hi][q]=min(dp[lo][hi][q],dp[lo][k][1]+dp[k+1][hi][q-1]);
// if(k+1<=hi)dp[lo][hi][i]=min(dp[lo][hi][i],dp[lo][k][q]+dp[k+1][hi][i-q]+pref[hi]-pref[lo-1]);
if(l<=q and q<=r){
dp[lo][hi][1]=min(dp[lo][hi][1],dp[lo][hi][q]+pref[hi]-pref[lo-1]);
}
// }
}
}
}
}
//for(int i=1; i<=n; i++){
// for(int j=i; j<=n; j++){
// if(dp[i][j][1]!=1e18) cout<<i<<" "<<j<<" "<<dp[i][j][1]<<endl;
// }
// }
if(dp[1][n][1]==1e18) cout<<-1<<endl;
else cout<<dp[1][n][1]<<endl;
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3608kb
input:
3 2 2 1 2 3 3 2 3 1 2 3 4 3 3 1 2 3 4
output:
9 6 -1
result:
wrong answer 3rd lines differ - expected: '0', found: '-1'