QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #647549 | #5137. Tower | xianyu | WA | 418ms | 8856kb | C++14 | 1.5kb | 2024-10-17 14:42:01 | 2024-10-17 14:42:02 |
Judging History
answer
#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
#define x first
#define y second
#define endl '\n'
using namespace std;
mt19937 rnd(time(0));
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
const double PI=acos(-1);
const int N=5e2+10,M=500,MOD=998244353,NN=1e6+10;
LL a[N];
int n;
int m;
LL dp[N][3*N];
int T;
vector<LL>vec;
void init(){
for(int i=0;i<=n;i++){
for(int j=0;j<vec.size();j++){
dp[i][j]=1e14;
}
}
for(int i=1;i<=n;i++){
for(int k=0;k<=32;k++){
for(int j=0;j<vec.size();j++){
LL cur=a[i];
cur=cur>>k;
dp[i][j]=min(dp[i][j],(LL)k+abs(cur-vec[j]));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
vec.push_back(a[i]+1);
vec.push_back(a[i]);
vec.push_back(a[i]-1);
}
init();
LL ans=1e18;
for(int i=0;i<vec.size();i++){//最后变成i
vector<LL>v;
for(int j=1;j<=n;j++){
v.push_back(dp[j][i]);
}
sort(v.begin(),v.end());
LL cur=0;
for(int j=1;j<=n-m;j++){
cur+=v[j-1];
}
ans=min(ans,cur);
}
cout<<ans<<endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
3 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5
output:
2 4 1
result:
ok 3 number(s): "2 4 1"
Test #2:
score: -100
Wrong Answer
time: 418ms
memory: 8856kb
input:
10 272 118 11 14 49 94 71 62 46 45 74 22 15 36 7 37 27 35 96 85 75 78 76 64 23 59 17 35 71 28 96 82 5 66 2 48 57 31 88 10 61 73 79 23 19 52 39 76 48 98 5 39 48 51 90 90 60 27 47 24 24 56 48 27 39 21 38 18 20 9 62 83 47 15 51 22 73 74 7 80 64 60 86 74 59 7 84 38 99 31 42 60 52 41 63 88 59 90 77 40 68...
output:
454 3 334 77 374 445 613 135 403 13
result:
wrong answer 3rd numbers differ - expected: '436', found: '334'