QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#445095 | #8774. Manhattan Walk | cry# | AC ✓ | 19ms | 19104kb | C++14 | 3.9kb | 2024-06-15 23:29:12 | 2024-06-15 23:29:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const int INF = 1E9;
// M
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// int n; int ii; int t;
// cin >> n >> ii >> t;
// vector<array<int, 4>> it(n);
// for(int i = 0; i < n; i++) {
// cin >> it[i][0] >> it[i][1] >> it[i][2] >> it[i][3];
// }
// vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
// dp[0][0] = 0;
// for(int i = 0; i < n; i++) {
// for(int j = 0; j <= i; j++) {
// if(dp[i][j] != -1) {
// int ti = ii + j;
// int tt = t + dp[i][j] - j;
// if(ti >= it[i][0] && ti <= it[i][1] && tt >= it[i][2] && tt <= it[i][3]) {
// dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
// dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
// }
// dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
// }
// }
// }
// int ans = 0;
// for(int i = 0; i <= n; i++) {
// ans = max(ans, dp[n][i]);
// }
// cout << ans << "\n";
// }
int main() {
cin.tie(0)->sync_with_stdio(0);
int r,c;
cout << fixed << setprecision(10);
long double p;
cin >> r >> c >> p;
vector<vector<long double>> dp(r, vector<long double>(c));
for(int x = c-2; x >= 0; x--) {
dp[r-1][x]=dp[r-1][x+1]+p/4;
}
for(int x = r-2; x >= 0; x--) {
dp[x][c-1]=dp[x+1][c-1]+p/4;
}
for(int row = r-2; row >= 0; row--) {
for(int col = c-2; col >= 0; col--) {
long double stratChange = abs(dp[row+1][col]-dp[row][col+1]);
if(stratChange<p) {
long double chance = stratChange/p;
dp[row][col]+=min(dp[row+1][col],dp[row][col+1])*chance;
dp[row][col]+=chance*0.5*stratChange/2;
dp[row][col]+=(1-chance)*0.5*min(dp[row+1][col], dp[row][col+1]);
dp[row][col]+=(1-chance)*0.5*max(dp[row+1][col], dp[row][col+1]);
} else {
//always wait
dp[row][col]=min(dp[row+1][col], dp[row][col+1])+p/4;
}
}
}
cout << dp[0][0] << endl;
}
//B222
// int main() {
// cin.tie(0)->sync_with_stdio(0);
// int t;
// cin >> t;
// while(t--) {
// string s;
// cin >> s;
// // vector<set<int>> digits(10);
// // for(int i = 0; i < s.size(); i++) {
// // if(s[i]=='?') continue;
// // digits[s[i]-'0'].insert(i);
// // }
// long long ans = 1<<30;
// //special case
// string start = "";
// for(int i = 1; i <= 999; i++) {
// start+=to_string(i);
// }
// for(int st = 0; st < start.size(); ++) {
// int end = st+s.size()-1;
// if(end>=start.size()) {
// break;
// }
// bool works = true;
// for(int moves = 0; moves < s.size(); moves++) {
// if(start[st+moves]==s[moves]||s[moves]=='?') {
// } else {
// works = false;
// break;
// }
// }
// if(works) {
// ans=st+1;
// break;
// }
// }
// if(ans!=(1<<30)) {
// cout << ans << "\n";
// continue;
// }
// //does not change digits
// for(int digits = 3; digits < 30; digits++) {
// for(int left = 0; left < digits; left++) {
// bool works = true;
// int change = -1;
// for(int x = 0; x < digits; x++) {
// if(left+x==digits-1) {
// int cur=-1;
// for(int y = x; y < s.size(); y+=digits) {
// if(s[y]!='?') {
// if(cur==-1) {
// cur=s[y]-'0';
// //look for change
// int tempcur = cur;
// for(int z = y; z >= digits; z-=digits) {
// if(tempcur==0) {
// int tempchange = z+1-digits;
// if(change==-1) {
// change=tempchange;
// } else if(change!=tempchange) {
// works=false;
// }
// }
// tempcur--;
// }
// } else {
// if(cur!=s[y]-'0') works=false;
// }
// }
// if(cur!=-1) {
// cur++;
// cur%=10;
// }
// }
// } else {
// }
// }
// }
// }
// }
// }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3736kb
input:
2 3 8
output:
2.8750000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 5 5
output:
2.4322338689
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
1 1 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 19ms
memory: 19104kb
input:
1000 1000 1000000000
output:
1782317138.8083752516
result:
ok found '1782317138.8083754', expected '1782317138.8083761', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
1 4 5
output:
3.7500000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 1 5
output:
3.7500000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 1000000000
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
1 2 1000000000
output:
250000000.0000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 1 1000000000
output:
250000000.0000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
1 2 1
output:
0.2500000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
2 1 1
output:
0.2500000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 10 3
output:
6.7500000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
10 1 3
output:
6.7500000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 11ms
memory: 18904kb
input:
997 993 998244353
output:
1779941051.3461624379
result:
ok found '1779941051.3461623', expected '1779941051.3461628', error '0.0000000'
Test #15:
score: 0
Accepted
time: 3ms
memory: 8348kb
input:
988 313 886183312
output:
78753022570.4833192229
result:
ok found '78753022570.4833221', expected '78753022570.4833527', error '0.0000000'
Test #16:
score: 0
Accepted
time: 4ms
memory: 5972kb
input:
583 286 322190846
output:
8636356976.8437140211
result:
ok found '8636356976.8437138', expected '8636356976.8437138', error '0.0000000'
Test #17:
score: 0
Accepted
time: 6ms
memory: 9872kb
input:
892 468 494964816
output:
17125998682.7292389553
result:
ok found '17125998682.7292385', expected '17125998682.7292328', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4164kb
input:
26 882 386682745
output:
78231677700.7504219860
result:
ok found '78231677700.7504272', expected '78231677700.7504883', error '0.0000000'
Test #19:
score: 0
Accepted
time: 14ms
memory: 15872kb
input:
867 926 422131798
output:
945100500.3991072662
result:
ok found '945100500.3991072', expected '945100500.3991071', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
37 68 19
output:
62.2844598802
result:
ok found '62.2844599', expected '62.2844599', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
23 90 80
output:
860.0506987358
result:
ok found '860.0506987', expected '860.0506987', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
43 55 85
output:
118.3892679676
result:
ok found '118.3892680', expected '118.3892680', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
93 66 43
output:
97.9048408588
result:
ok found '97.9048409', expected '97.9048409', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
78 93 30
output:
44.8454523265
result:
ok found '44.8454523', expected '44.8454523', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
9 5 481032867
output:
400507342.3667383420
result:
ok found '400507342.3667383', expected '400507342.3667384', error '0.0000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
366 73 3
output:
149.4864642331
result:
ok found '149.4864642', expected '149.4864642', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
6 4 5
output:
2.8946451697
result:
ok found '2.8946452', expected '2.8946452', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
8 10 5
output:
3.3973608525
result:
ok found '3.3973609', expected '3.3973609', error '0.0000000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
10 1 7
output:
15.7500000000
result:
ok found '15.7500000', expected '15.7500000', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
10 7 10
output:
7.3716466074
result:
ok found '7.3716466', expected '7.3716466', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 8 1
output:
1.3271069195
result:
ok found '1.3271069', expected '1.3271069', error '0.0000000'