#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr int INF = 1e4;
struct Vertex{
int v, now, tot, p, on, tor;
Vertex(){}
Vertex(int _v, int _n, int _tot, int _p, int _on, int _tor): v(_v), now(_n), tot(_tot), p(_p), on(_on), tor(_tor) {}
bool operator < (const Vertex &V) const{return tor > V.tor;}
};
int a[500500], L[500500], R[500500], nxt[500500];
short dist[303][303][303][3][2];
vector<int> V;
int get_left(int i){
assert(a[i]!=-1);
if (i < V[0]) return -INF;
return (*--lower_bound(V.begin(), V.end(), i));
}
int get_right(int i){
assert(a[i]!=-1);
if (i > V.back()) return INF;
return (*lower_bound(V.begin(), V.end(), i));
}
int main(){
int n, s = INF;
scanf("%d", &n);
ll ans = 0;
for (int i=0;i<n;i++){
scanf("%d", a+i);
if (a[i]==-1) V.push_back(i);
else ans += a[i], s = min(s, i);
}
if (s==INF) {printf("0\n"); return 0;}
///init
int prv = -1;
for (int i=0;i<n;i++) if (a[i]!=-1){
L[i] = get_left(i), R[i] = get_right(i);
nxt[i] = INF;
//printf("%d -> %d %d %d\n", i, L[i], R[i], nxt[i]);
if (prv!=-1) nxt[prv] = i;
prv = i;
}
for (int i=0;i<303;i++){
for (int j=0;j<303;j++){
for (int k=0;k<303;k++){
for (int l=0;l<3;l++){
for (int z=0;z<2;z++) dist[i][j][k][l][z] = INF;
}
}
}
}
priority_queue<Vertex> pq;
dist[s][0][0][0][0] = s;
pq.emplace(s, 0, 0, 0, 0, s);
int rans = 0;
while(!pq.empty()){
auto [v, now, tot, p, on, tor] = pq.top(); pq.pop();
if (dist[v][now][tot][p][on] != tor) continue;
//printf("%d %d %d %d %d -> %d\n", v, now, tot, p, on, tor);
rans = max(rans, tot);
int nv = nxt[v], rv = v;
if (p==1) rv = L[v];
if (p==2) rv = R[v];
if (nv!=INF && dist[nv][0][tot][0][on] > tor + nv-rv){
dist[nv][0][tot][0][on] = tor + nv-rv;
pq.emplace(nv, 0, tot, 0, on, tor + nv-rv);
}
if (!on){
if (p==0){
if (now < a[v] && tor <= v*2){
if (dist[v][now+1][tot+1][0][1] > tor){
dist[v][now+1][tot+1][0][1] = tor;
pq.emplace(v, now+1, tot+1, 0, 1, tor);
}
}
}
else{
if (dist[v][now][tot][0][0] > tor + abs(rv-v)){
dist[v][now][tot][0][0] = tor + abs(rv-v);
pq.emplace(v, now, tot, 0, 0, tor + abs(rv-v));
}
}
}
else{
if (p==0){
if (dist[v][now][tot][1][1] > tor + abs(L[v]-v)){
dist[v][now][tot][1][1] = tor + abs(L[v]-v);
pq.emplace(v, now, tot, 1, 1, tor + abs(L[v]-v));
}
if (dist[v][now][tot][2][1] > tor + abs(R[v]-v)){
dist[v][now][tot][2][1] = tor + abs(R[v]-v);
pq.emplace(v, now, tot, 2, 1, tor + abs(R[v]-v));
}
}
else{
if (dist[v][now][tot][p][0] > tor){
dist[v][now][tot][p][0] = tor;
pq.emplace(v, now, tot, p, 0, tor);
}
}
}
}
printf("%lld\n", ans - rans);
return 0;
}
Compilation message
tortoise.cpp: In function 'int main()':
tortoise.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
tortoise.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
326908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
326908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
326908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
326908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
326908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
