QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648061#9220. Bus AnalysisBINYUWA 470ms9448kbC++141.0kb2024-10-17 16:51:342024-10-17 16:51:35

Judging History

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

  • [2024-10-17 16:51:35]
  • 评测
  • 测评结果:WA
  • 用时:470ms
  • 内存:9448kb
  • [2024-10-17 16:51:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000;
const ll mod = 1e9 + 7;
int n,a[N + 5];
ll dp[2][75][75][75],ans,f[N + 5] = {1};
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
		scanf("%d",&a[i]),f[i] = f[i - 1] * 2 % mod;
	dp[0][0][0][0] = 2;
	for(int i = 1;i <= n;i++)
	{
		int o = i & 1;
		for(int j0 = 0;j0 <= 70;j0++)
		for(int j1 = j0;j1 <= 70;j1++)
		for(int j2 = j1;j2 <= 70;j2++)
			dp[o][j0][j1][j2] = 0;
		for(int j0 = 0;j0 <= 70;j0++)
		for(int j1 = j0;j1 <= 70;j1++)
		for(int j2 = j1;j2 <= 70;j2++)
		{
			int nj0 = max(0,j0 - (a[i] - a[i - 1])); 
			int nj1 = max(nj0 + 20,j1 - (a[i] - a[i - 1])); 
			int nj2 = max(nj1 + 20,j2 - (a[i] - a[i - 1]));
			int nj3 = max(nj0 + 70,nj2 + 20);
			(dp[o][nj0][nj1][nj2] += dp[o ^ 1][j0][j1][j2]) %= mod;
			if(!nj0)
				(dp[o][nj1][nj2][nj3] += dp[o ^ 1][j0][j1][j2]) %= mod,
				(ans += dp[o ^ 1][j0][j1][j2] * f[n - i]) %= mod;
			else (dp[o][nj0][nj1][nj2] += dp[o ^ 1][j0][j1][j2]) %= mod;
		}
	}
	cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9448kb

input:

3
1 8 20

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 2ms
memory: 9432kb

input:

5
25 45 65 85 1000000000

output:

156

result:

ok 1 number(s): "156"

Test #3:

score: -100
Wrong Answer
time: 470ms
memory: 8044kb

input:

1000
2 7 9 12 14 17 18 21 22 28 29 33 34 35 37 38 44 45 46 50 58 59 63 66 71 72 75 76 77 78 80 81 83 84 87 92 100 101 107 108 109 112 114 116 118 123 124 131 142 143 144 145 148 150 151 152 153 155 157 158 165 167 168 169 171 176 182 185 190 192 198 202 204 205 212 213 223 224 225 226 229 231 240 24...

output:

567111684

result:

wrong answer 1st numbers differ - expected: '932594593', found: '567111684'