QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345941 | #8305. Accelerator | black_moonrise# | WA | 8ms | 181948kb | C++14 | 2.0kb | 2024-03-07 17:31:12 | 2024-03-07 17:31:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
const int maxn = 211;
double calc(int down, int up, int l, int r) {
// (0, l) -> (1, r) intersect [down, up]
if(l >= r) swap(l, r);
down = max(down, l);
up = min(up, r);
if(up <= down) return 0.0;
double q1 = 1.0 * (r - up) / (r - l);
double q2 = 1.0 * (r - down) / (r - l);
return (q1 + q2) * (up - down) / 2;
}
double f[211][1024], dp[211][211][512];
int n, h[211], W, H;
int main() {
printf("hehe %.10lf\n", calc(0, 5, 0, 5));
scanf("%d%d%d", &n, &W, &H);
for(int i=1; i<=n; i++) scanf("%d", h+i);
for(int i=0; i<=n; i++) {
for(int j=0; j<(1<<W*2); j++) {
vector<pair<int, int> > vs;
for(int k=0; k<W*2; k++) if((j >> k) & 1) {
// [i - W+ 1, i + W]
int pos = i + W - k;
if(pos >= 0 && pos <= n+1) {
vs.emplace_back(h[pos] - H, h[pos] + H);
}
}
sort(vs.begin(), vs.end());
int cur = -1e9;
for(auto v : vs) {
// max(v.ff, cur) -> v.ss
if(cur < v.ss) {
f[i][j] += calc(max(cur, v.ff), v.ss, h[i], h[i+1]);
cur = v.ss;
}
}
printf("i= %d j= %d f= %.2lf\n", i, j, f[i][j]);
}
}
for(int i=0; i<211; i++) for(int j=0; j<211; j++) for(int k=0; k<512; k++) dp[i][j][k] = -1e100;
dp[1][0][0] = 0.0;
int tot_mask = (1 << W*2) - 1;
for(int i=1; i<=n + W; i++) {
for(int j=0; j<i; j++) {
for(int mask=0; mask<(1<<W*2-1); mask++) {
if(dp[i][j][mask] < 0) continue;
// decided: [i - W*2 + 1, i]
for(int t=0; t<1 + (i <= n); t++) {
int nmask = (mask * 2 + t) & tot_mask;
dp[i+1][j+t][nmask] = max(dp[i+1][j+t][nmask], dp[i][j][mask] + (i >= W ? f[i-W][mask*2+t] : 0));
}
printf("i= %d j= %d mask= %d dp= %.2lf\n", i, j, mask, dp[i][j][mask]);
}
}
}
printf("n= %d\n", n);
for(int j=1; j<=n; j++) {
double ans = 0;
for(int k=0; k<(1<<W*2-1); k++) {
ans = max(ans, dp[n+W][j][k]);
}
printf("%.10lf\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 181948kb
input:
3 3 1 2 3 1 10 4 5 5 5 5
output:
hehe 2.5000000000 i= 0 j= 0 f= 0.00 i= 0 j= 1 f= 1.00 i= 0 j= 2 f= 0.00 i= 0 j= 3 f= 1.00 i= 0 j= 4 f= 0.25 i= 0 j= 5 f= 1.00 i= 0 j= 6 f= 0.25 i= 0 j= 7 f= 1.00 i= 0 j= 8 f= 0.75 i= 0 j= 9 f= 1.00 i= 0 j= 10 f= 0.75 i= 0 j= 11 f= 1.00 i= 0 j= 12 f= 1.00 i= 0 j= 13 f= 1.00 i= 0 j= 14 f= 1.00 i= 0 j=...
result:
wrong answer 1st lines differ - expected: '665496247', found: 'hehe 2.5000000000'