QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #258279 | #5537. Storing Eggs | hank55663# | WA | 2ms | 8572kb | C++14 | 4.2kb | 2023-11-19 16:42:51 | 2023-11-19 16:42:53 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acos(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
int dp[105][105][105];
char c[105][105];
void solve(int T){
int n,k;
scanf("%d %d",&n,&k);
vector<LL> ans;
for(int i = 1;i<n;i++){
for(int j = 0;j<3;j++){
if(i*i+j+j!=1)
ans.pb(i*i+j*j);
}
}
int tot=0;
for(int i = 0;i<3;i++){
scanf("%s",c[i]+1);
for(int j = 1;j<=n;j++){
if(c[i][j]=='.')tot++;
}
}
if(tot<k){
printf("-1\n");
return;
}
sort(ans.begin(),ans.end());
int Min=-1,Max=ans.size();
while(Max>Min+1){
int mid=ans[(Max+Min)/2];
// printf("%d\n",mid);
MEM(dp);
for(int i = 1;i<=n;i++){
int aa=0;
while((i-aa-1)*(i-aa-1)>=mid&&aa<i)aa++;
if(c[0][i]=='.'){
for(int j = 0;(1+(i-j)*(i-j)>=mid||j==0)&&j<i;j++){
for(int k =0;(4+(i-k)*(i-k)>=mid||k==0)&&k<i;k++){
dp[i][j][k]=max(dp[aa][j][k]+1,dp[i][j][k]);
}
}
}
if(c[1][i]=='.'){
for(int j = 0;(1+(i-j)*(i-j)>=mid||j==0)&&j<i;j++){
for(int k =0;(1+(i-k)*(i-k)>=mid||k==0)&&k<i;k++){
//if(mid==8)
// printf("??%d %d %d %d\n",j,i,aa,k);
dp[j][i][k]=max(dp[j][aa][k]+1,dp[j][i][k]);
}
}
}
if(c[2][i]=='.'){
for(int j = 0;(1+(i-j)*(i-j)>=mid||j==0)&&j<i;j++){
for(int k =0;(4+(i-k)*(i-k)>=mid||k==0)&&k<i;k++){
dp[k][j][i]=max(dp[k][j][aa]+1,dp[k][j][i]);
}
}
}
if(c[0][i]=='.'&&c[2][i]=='.'&&mid<=2){
for(int j = 0;1+(i-j)*(i-j)>=mid||j==0;j++){
dp[i][j][i]=max(dp[aa][j][aa]+2,dp[i][j][i]);
// printf("%d %d %d %d %d %d\n",i,j,i,aa,dp[i][j][i],dp[aa][j][aa]);
}
}
for(int j = 0;j<=i;j++){
for(int k=0;k<=i;k++){
if(i)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
if(j)
dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
if(k)
dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]);
swap(i,j);
if(i)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
if(j)
dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
if(k)
dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]);
swap(i,j);
swap(i,k);
if(i)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
if(j)
dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
if(k)
dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]);
swap(i,k);
}
}
}
if(mid==8)
for(int i = 0;i<=3;i++){
for(int j = 0;j<=3;j++){
for(int k=0;k<=3;k++){
if(dp[i][j][k]>=2)printf("%d %d %d\n",i,j,k);
}
}
}
// printf("%d %d %d\n",dp[3][3][3],dp[3][0][1],dp[1][0][3]);
// printf("%d\n",dp[n][n][n]);
if(dp[n][n][n]>=k)Min=(Max+Min)/2;
else Max=(Max+Min)/2;
}
if(Min==-1){
printf("1\n");
return;
}
printf("%.12f\n",sqrt(ans[Min]));
}
int main(){
int t=1;
//scanf("%d",&t);
for(int i = 1;i<=t;i++){
// cerr<<i<<endl;
solve(i);
}
}
/*
1227076727
1919786269
1261786217
1924134973
1051246577
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8256kb
input:
5 2 #.... ..... ....#
output:
4.472135955000
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 8332kb
input:
5 6 ##.## ##### .....
output:
1
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8572kb
input:
3 4 ..# ... ...
output:
1.414213562373
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3980kb
input:
1 2 . . .
output:
1
result:
wrong answer 1st numbers differ - expected: '2.0000000', found: '1.0000000', error = '0.5000000'