QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #177829 | #5537. Storing Eggs | dj4zo6u_6 | WA | 8ms | 4076kb | C++14 | 4.7kb | 2023-09-13 14:18:11 | 2023-09-13 14:18:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
void solve();
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
}
int n,k;
bool a[3][105];
int dp[105][10];
void upd(int &a,vector<int>v){
for(int b:v)a=max(a,b);
}
int cnt(int dis){
for(int i=0;i<n+5;i++)for(int j=0;j<10;j++)dp[i][j]=0;
if(dis==1){
int ret=0;
for(int i=0;i<3;i++)for(int j=1;j<=n;j++)ret+=a[i][j];
return ret;
}
if(dis==2){
for(int i=1;i<=n;i++){
dp[i][0]=0; for(int j=1;j<4;j++)dp[i][j]=1; dp[i][4]=2;
for(int j=0;j<5;j++)upd(dp[i][0],{dp[i-1][j]});
upd(dp[i][1], {dp[i-1][0]+1, dp[i-1][2]+1, dp[i-1][3]+1});
upd(dp[i][2], {dp[i-1][0]+1, dp[i-1][1]+1, dp[i-1][3]+1, dp[i-1][4]+1});
upd(dp[i][3], {dp[i-1][0]+1, dp[i-1][1]+1, dp[i-1][2]+1});
upd(dp[i][4], {dp[i-1][0]+2, dp[i-1][2]+2});
if(!a[0][i])dp[i][1]--,dp[i][4]--;
if(!a[1][i])dp[i][2]--;
if(!a[2][i])dp[i][3]--,dp[i][4]--;
}
int ret=0;
for(int j=0;j<5;j++)upd(ret,{dp[n][j]});
return ret;
}
if(dis<=4){
for(int i=1;i<=n;i++){
dp[i][0]=0; for(int j=1;j<4;j++)dp[i][j]=1; dp[i][4]=2;
for(int j=0;j<5;j++)upd(dp[i][0],{dp[i-1][j]});
// for(int j=1;j<4;j++)upd(dp[i][j],{dp[i-1][0]+1});
upd(dp[i][1],{dp[i-1][0]+1,dp[i-1][3]+1});
upd(dp[i][2],{dp[i-1][0]+1});
upd(dp[i][3],{dp[i-1][0]+1,dp[i-1][1]+1});
upd(dp[i][4],{dp[i-1][0]+2});
if(!a[0][i])dp[i][1]--,dp[i][4]--;
if(!a[1][i])dp[i][2]--;
if(!a[2][i])dp[i][3]--,dp[i][4]--;
}
int ret=0;
for(int j=0;j<5;j++)upd(ret,{dp[n][j]});
return ret;
}
if(dis==5){
for(int i=(2-(n&1));i<=n;i+=2){
dp[i][0]=0; for(int j=1;j<7;j++)dp[i][j]=1; for(int j:{7,8})dp[i][j]=2;
if(i>=2){
for(int j=0;j<9;j++)upd(dp[i][0],{dp[i-2][j]});
upd(dp[i][1], {dp[i-2][0]+1, dp[i-2][2]+1, dp[i-2][3]+1, dp[i-2][6]+1});
upd(dp[i][2], {dp[i-2][0]+1, dp[i-2][1]+1, dp[i-2][3]+1});
upd(dp[i][3], {dp[i-2][0]+1, dp[i-2][1]+1, dp[i-2][2]+1, dp[i-2][4]+1});
for(int j:{4,5,6})for(int k:{0,1,2,3})upd(dp[i][j], {dp[i-2][k]+1});
upd(dp[i][4], {dp[i-2][5]+1, dp[i-2][6]+1});
upd(dp[i][5], {dp[i-2][4]+1, dp[i-2][6]+1});
upd(dp[i][6], {dp[i-2][4]+1, dp[i-2][5]+1});
upd(dp[i][7], {dp[i-2][0]+2, dp[i-2][2]+2, dp[i-2][3]+2});
upd(dp[i][8], {dp[i-2][0]+2, dp[i-2][1]+2, dp[i-2][2]+2});
}
if(!a[0][i-1])dp[i][1]--,dp[i][7]--;
if(!a[1][i-1])dp[i][2]--;
if(!a[2][i-1])dp[i][3]--,dp[i][8]--;
if(!a[0][i])dp[i][4]--,dp[i][8]--;
if(!a[1][i])dp[i][5]--;
if(!a[2][i])dp[i][6]--,dp[i][7]--;
}
int ret=0;
for(int j=0;j<9;j++)upd(ret,{dp[n][j]});
return ret;
}
else{
for(int i=1;i<=n;i++){
dp[i][0]=0; for(int j=1;j<4;j++)dp[i][j]=1;
for(int j=0;j<4;j++)upd(dp[i][0],{dp[i-1][j]});
for(int j=1;j<i;j++){
int d=i-j;
if(d*d+4<dis)break;
if(d*d>=dis){
for(int k=1;k<4;k++)upd(dp[i][k],{dp[j+1][0]+1});
}
if(d*d+1>=dis){
upd(dp[i][1],{dp[j][0]+1,dp[j][2]+1,dp[j][3]+1});
upd(dp[i][2],{dp[j][0]+1,dp[j][1]+1,dp[j][3]+1});
upd(dp[i][3],{dp[j][0]+1,dp[j][1]+1,dp[i][2]+1});
}
if(d*d+4>=dis){
upd(dp[i][1],{dp[j][0]+1,dp[j][3]+1});
upd(dp[i][3],{dp[j][0]+1,dp[j][1]+1});
}
}
if(!a[0][i])dp[i][1]--;
if(!a[1][i])dp[i][2]--;
if(!a[2][i])dp[i][3]--;
}
int ret=0;
for(int j=0;j<4;j++)upd(ret,{dp[n][j]});
return ret;
}
}
int serch(int l,int r){
if(r-l<2)return l;
int m=(l+r)/2;
if(cnt(m)>=k)return serch(m,r);
return serch(l,m);
}
void solve(){
cin>>n>>k;
for(int i=0;i<3;i++){
string s;cin>>s;
for(int j=1,t=0;t<n;j++,t++)a[i][j]=(s[t]=='.');
}
if(cnt(1)<k){
cout<<"-1\n";
return;
}
for(int i=1;i<=20;i++)cerr<<cnt(i)<<",\n"[i==20];
int ans=serch(1,n*n*2+10);
cerr<<ans<<"\n";
cout<<fixed<<setprecision(15)<<(long double)sqrt(ans)<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3844kb
input:
5 2 #.... ..... ....#
output:
4.472135954999580
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 6 ##.## ##### .....
output:
1.000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 4 ..# ... ...
output:
1.414213562373095
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
1 2 . . .
output:
2.000000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 8ms
memory: 4076kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.020199959402220
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 7ms
memory: 3984kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.005050376230813
result:
wrong answer 1st numbers differ - expected: '49.0407990', found: '99.0050504', error = '1.0188303'