QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#345941#8305. Acceleratorblack_moonrise#WA 8ms181948kbC++142.0kb2024-03-07 17:31:122024-03-07 17:31:12

Judging History

你现在查看的是最新测评结果

  • [2024-03-07 17:31:12]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:181948kb
  • [2024-03-07 17:31:12]
  • 提交

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'