QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760350 | #3040. Container | czc | WA | 0ms | 9548kb | C++23 | 2.8kb | 2024-11-18 16:25:27 | 2024-11-18 16:25:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int C,n,c;
char a[maxn],b[maxn];
vector<int> pos1,pos2[maxn];
int f[maxn][maxn],pre[maxn][maxn];
inline int g(int d){
return (d/2)*(c+4)+(d%2)*(c+3);
}
int sum[2][maxn][maxn];
int main(){
scanf("%d%d%d",&C,&n,&c);
scanf("%s",a+1);
scanf("%s",b+1);
for(int i=1;i<=n;i++){
if(a[i]=='B') pos1.push_back(i);
if(b[i]=='B'){
pos2[i%2].push_back(i);
}
}
for(int op=0;op<2;op++){
for(int i=0;i<pos2[op].size();i++){
for(int j=1;j<=n;j++){
if(i) sum[op][i][j]=sum[op][i-1][j];
sum[op][i][j]+=(pos2[op][i]>j);
}
}
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=(int)pos1.size();i++){
for(int j=0;j<=min((int)pos2[1].size(),i-1);j++){
if(f[i-1][j]==0x3f3f3f3f) continue;
if(j<pos2[1].size()){
//f i-1,j -> f i,j+1 match pos2[1][j] pos[i-1]
int s=g(abs(pos2[1][j]-pos1[i-1]));
int dl=(i-j-1)?sum[0][i-j-2][pos2[1][j]]:0;
if(f[i][j+1]>f[i-1][j]+s+dl){
f[i][j+1]=f[i-1][j]+s+dl;
pre[i][j+1]=1;
}
}
if(i-1-j<pos2[0].size()){
//f i-1,j -> f i,j match pos2[0][i-j-1] pos[i-1]
int s=g(abs(pos2[0][i-j-1]-pos1[i-1]));
int dl=j?sum[1][j-1][pos2[0][i-j-1]]:0;
if(f[i][j]>f[i-1][j]+s+dl){
f[i][j]=f[i-1][j]+s+dl;
pre[i][j]=0;
}
}
}
}
int m=pos1.size(),odd=pos2[1].size(),even=pos2[0].size();
vector< pair<int,int> > a[2];
while(m){
int pr=pre[m][odd];
if(pr==1){
m--,odd--;
int st=pos1[m],en=pos2[1][odd];
if(st<en) a[0].push_back({st,en});
else a[1].push_back({st,en});
}
else{
m--,even--;
int st=pos1[m],en=pos2[0][even];
if(st<en) a[0].push_back({st,en});
else a[1].push_back({st,en});
}
}
vector< pair<int,int> > ans;
for(auto y:a[0]){
int st=y.first,en=y.second;
while(st+2<=en){
ans.push_back({st,st+2});
st+=2;
}
if(st!=en) ans.push_back({st,en});
}
reverse(a[1].begin(),a[1].end());
for(auto y:a[1]){
int st=y.first,en=y.second;
while(st-2>=en){
ans.push_back({st-2,st});
st-=2;
}
if(st!=en) ans.push_back({en,st});
}
printf("%d\n",(int)ans.size());
for(auto x:ans) printf("%d %d\n",x.first,x.second);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9548kb
input:
5 2 11221 21112
output:
0
result:
wrong answer invalid plan.