QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #356483 | #7199. Bomb | vme50 | WA | 1ms | 8084kb | C++17 | 994b | 2024-03-17 21:04:50 | 2024-03-17 21:04:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+5;
int n,a[N];ll b[N],s[N],dp1[N][N],dp2[N][N];
void W(ll &x,ll y) {x=min(x,y);}
ll sqr(int x) {return 1ll*x*x;}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
b[0]=b[n]=1e18;for(int i=1;i<n;++i) b[i]=sqr(a[i]-a[i+1]);
for(int i=1;i<=n;++i) s[i]=s[i-1]+min(b[i],b[i-1]);
for(int i=1;i<=n;++i) for(int j=i;j<=n;++j)
dp1[i][j]=dp2[i][j]=1e18;dp1[1][1]=dp2[1][1]=0;
for(int i=1;i<=n;++i)
{
for(int j=n-1;j>=i;--j) W(dp2[i][j],dp2[i][j+1]);
for(int j=i;j<=n;++j)
{
if(i<j) W(dp1[i][j],dp2[i][j]+s[j-1]-s[i]);
if(j<n) W(dp1[i][j+1],dp1[i][j]+b[j]);
if(i<j) W(dp2[i+1][j],dp2[i][j]+b[i]);
}
for(int j=n,t=n;j>i;--j)
{
while(t && a[t]>a[j]*2-a[i]) --t;
W(dp2[j][t],dp1[i][j]+sqr(a[i]-a[j]));
if(t<n) W(dp2[j][t+1],dp1[i][j]+sqr(a[j]-a[t+1]));
}
}printf("%lld\n",dp2[n][n]);
}return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6012kb
input:
5 1 4 5 6 10 3 1 2 6
output:
51 33
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 8084kb
input:
18 1 2 3 6 11 23 47 106 235 551 1301 3159 7741 19320 48629 123867 317955 823065 5 1 5 6 7 11 2 1 1000000 3 1 12345 1000000 4 1 2 3 1000000
output:
554621353432 59 1999996000002 1951077172386 1999988000020
result:
ok 5 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 6040kb
input:
5 1 2 5 6 7 5 1 4 5 7 10 5 1 2 5 7 10 5 1 4 5 7 10 5 1 2 5 6 7 5 1 4 5 7 10 5 1 2 5 6 7 5 1 2 5 6 7 5 2 5 6 7 9 5 2 5 6 7 9 5 1 4 5 7 10 5 2 3 5 6 9 5 2 5 6 7 9 5 1 2 5 6 7 5 2 3 6 8 9 5 1 2 5 7 10 5 2 3 5 6 9 5 1 4 5 7 10 5 1 2 5 6 7 5 1 2 5 7 10 5 2 5 6 7 9 5 1 2 5 7 10 5 1 4 5 7 10 5 2 3 6 8 9 5 ...
output:
21 37 37 37 21 37 21 21 27 27 37 24 27 21 24 37 24 37 21 37 27 37 37 24 27 27 27 27 24 24 37 27 24 24 27 21 21 37 37 21 24 27 24 27 21 27 37 37 37 27 37 21 24 37 37 24 24 21 27 24 37 27 21 37 37 24 27 21 27 37 21 37 37 24 37 24 37 37 21 37 21 27 21 24 24 27 27 24 37 24 24 27 37 24 27 37 24 21 24 24
result:
ok 100 tokens
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 6012kb
input:
10 6 8 24 41 42 43 66 81 83 99 10 3 17 28 51 54 58 65 71 77 98 10 31 55 56 59 63 67 78 84 89 93 10 31 55 56 59 63 67 78 85 89 93 10 11 12 13 29 36 50 74 75 94 95 10 2 16 21 23 45 47 69 70 72 96 10 15 16 19 47 49 72 73 79 86 92 10 31 34 55 56 59 63 67 78 84 93 10 1 23 35 45 48 62 64 69 70 90 10 5 22 ...
output:
2158 2429 1392 1396 2225 2495 2233 1259 2188 2130 2027 2526 1418 1988 2188 2000 1428 2515 3627 2327 1348 2051 2158 1462 1988 2045 2083 2291 1462 2345 2333 1396 2258 2142 1428 2051 1538 2002 2363 2173 2276 2465 2118 1902 1538 2051 2069 2781 2118 2526 3579 2394 1196 2083 2033 2129 2129 2345 3579 2427 ...
result:
wrong answer 12th words differ - expected: '2529', found: '2526'