답안 #742389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742389	2023-05-16T08:09:33 Z	maomao90	Tortoise (CEOI21_tortoise)	C++17	0 / 100	209 ms	392608 KB

tortoise

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 5005;

int n;
int a[MAXN];
int lft[MAXN], rht[MAXN];
int dp[MAXN][MAXN * 4];
int ans;

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n;
    ll sm = 0;
    REP (i, 0, n) {
        cin >> a[i];
        sm += max(0, a[i]);
    }
    REP (i, 0, n) {
        if (a[i] == -1) {
            lft[i] = i;
        } else {
            lft[i] = i == 0 ? -INF : lft[i - 1];
        }
    }
    rht[n] = INF;
    RREP (i, n - 1, 0) {
        if (a[i] == -1) {
            rht[i] = i;
        } else {
            rht[i] = rht[i + 1];
        }
    }
    REP (i, 0, MAXN) {
        REP (j, 0, MAXN * 4) {
            dp[i][j] = -INF;
        }
    }
    dp[0][0] = 0;
    REP (i, 0, n) {
        REP (j, 0, i * 2 + 1) {
            mxto(dp[i + 1][j + 1], dp[i][j]);
            if (a[i] <= 0) {
                continue;
            }
            REP (k, 1, a[i] + 1) {
                int near = min(i - lft[i], rht[i] - i);
                ll nj = j + (ll) near * 2 * (k - 1);
                if (nj > i * 2) {
                    break;
                }
                mxto(ans, dp[i][j] + k);
                if (lft[i] != -INF) {
                    mxto(dp[i + 1][nj + i - lft[i] + i + 1 - lft[i]],
                            dp[i][j] + k);
                }
                if (rht[i] != INF) {
                    RREP (l, rht[i], i + 1) {
                        mxto(dp[l][nj + rht[i] - i + rht[i] - l], dp[i][j] + k);
                    }
                }
            }
        }
    }
    cout << sm - ans << '\n';
    return 0;
}

Subtask #1

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	392368 KB	Output is correct
2	Correct	178 ms	392488 KB	Output is correct
3	Correct	168 ms	392440 KB	Output is correct
4	Correct	164 ms	392476 KB	Output is correct
5	Correct	167 ms	392436 KB	Output is correct
6	Correct	179 ms	392532 KB	Output is correct
7	Correct	178 ms	392460 KB	Output is correct
8	Correct	179 ms	392436 KB	Output is correct
9	Correct	182 ms	392608 KB	Output is correct
10	Correct	169 ms	392464 KB	Output is correct
11	Correct	170 ms	392456 KB	Output is correct
12	Correct	170 ms	392404 KB	Output is correct
13	Correct	172 ms	392392 KB	Output is correct
14	Correct	176 ms	392400 KB	Output is correct
15	Correct	209 ms	392512 KB	Output is correct
16	Correct	168 ms	392396 KB	Output is correct
17	Correct	178 ms	392524 KB	Output is correct
18	Correct	171 ms	392436 KB	Output is correct
19	Correct	174 ms	392560 KB	Output is correct
20	Incorrect	173 ms	392412 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	392368 KB	Output is correct
2	Correct	178 ms	392488 KB	Output is correct
3	Correct	168 ms	392440 KB	Output is correct
4	Correct	164 ms	392476 KB	Output is correct
5	Correct	167 ms	392436 KB	Output is correct
6	Correct	179 ms	392532 KB	Output is correct
7	Correct	178 ms	392460 KB	Output is correct
8	Correct	179 ms	392436 KB	Output is correct
9	Correct	182 ms	392608 KB	Output is correct
10	Correct	169 ms	392464 KB	Output is correct
11	Correct	170 ms	392456 KB	Output is correct
12	Correct	170 ms	392404 KB	Output is correct
13	Correct	172 ms	392392 KB	Output is correct
14	Correct	176 ms	392400 KB	Output is correct
15	Correct	209 ms	392512 KB	Output is correct
16	Correct	168 ms	392396 KB	Output is correct
17	Correct	178 ms	392524 KB	Output is correct
18	Correct	171 ms	392436 KB	Output is correct
19	Correct	174 ms	392560 KB	Output is correct
20	Incorrect	173 ms	392412 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	392368 KB	Output is correct
2	Correct	178 ms	392488 KB	Output is correct
3	Correct	168 ms	392440 KB	Output is correct
4	Correct	164 ms	392476 KB	Output is correct
5	Correct	167 ms	392436 KB	Output is correct
6	Correct	179 ms	392532 KB	Output is correct
7	Correct	178 ms	392460 KB	Output is correct
8	Correct	179 ms	392436 KB	Output is correct
9	Correct	182 ms	392608 KB	Output is correct
10	Correct	169 ms	392464 KB	Output is correct
11	Correct	170 ms	392456 KB	Output is correct
12	Correct	170 ms	392404 KB	Output is correct
13	Correct	172 ms	392392 KB	Output is correct
14	Correct	176 ms	392400 KB	Output is correct
15	Correct	209 ms	392512 KB	Output is correct
16	Correct	168 ms	392396 KB	Output is correct
17	Correct	178 ms	392524 KB	Output is correct
18	Correct	171 ms	392436 KB	Output is correct
19	Correct	174 ms	392560 KB	Output is correct
20	Incorrect	173 ms	392412 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	392368 KB	Output is correct
2	Correct	178 ms	392488 KB	Output is correct
3	Correct	168 ms	392440 KB	Output is correct
4	Correct	164 ms	392476 KB	Output is correct
5	Correct	167 ms	392436 KB	Output is correct
6	Correct	179 ms	392532 KB	Output is correct
7	Correct	178 ms	392460 KB	Output is correct
8	Correct	179 ms	392436 KB	Output is correct
9	Correct	182 ms	392608 KB	Output is correct
10	Correct	169 ms	392464 KB	Output is correct
11	Correct	170 ms	392456 KB	Output is correct
12	Correct	170 ms	392404 KB	Output is correct
13	Correct	172 ms	392392 KB	Output is correct
14	Correct	176 ms	392400 KB	Output is correct
15	Correct	209 ms	392512 KB	Output is correct
16	Correct	168 ms	392396 KB	Output is correct
17	Correct	178 ms	392524 KB	Output is correct
18	Correct	171 ms	392436 KB	Output is correct
19	Correct	174 ms	392560 KB	Output is correct
20	Incorrect	173 ms	392412 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	179 ms	392368 KB	Output is correct
2	Correct	178 ms	392488 KB	Output is correct
3	Correct	168 ms	392440 KB	Output is correct
4	Correct	164 ms	392476 KB	Output is correct
5	Correct	167 ms	392436 KB	Output is correct
6	Correct	179 ms	392532 KB	Output is correct
7	Correct	178 ms	392460 KB	Output is correct
8	Correct	179 ms	392436 KB	Output is correct
9	Correct	182 ms	392608 KB	Output is correct
10	Correct	169 ms	392464 KB	Output is correct
11	Correct	170 ms	392456 KB	Output is correct
12	Correct	170 ms	392404 KB	Output is correct
13	Correct	172 ms	392392 KB	Output is correct
14	Correct	176 ms	392400 KB	Output is correct
15	Correct	209 ms	392512 KB	Output is correct
16	Correct	168 ms	392396 KB	Output is correct
17	Correct	178 ms	392524 KB	Output is correct
18	Correct	171 ms	392436 KB	Output is correct
19	Correct	174 ms	392560 KB	Output is correct
20	Incorrect	173 ms	392412 KB	Output isn't correct
21	Halted	0 ms	0 KB	-