oj.uz

Submission #968268

# Submission time Handle Problem Language Result Execution time Memory
968268 2024-04-23T09:09:31 Z Pring Line Town (CCO23_day1problem3) C++17
4 / 25
 48 ms 31720 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 2005, INF = 1e9;
int n, a[MXN];
int alive[MXN];
pii dist[MXN];
int dpl[MXN][MXN], dpr[MXN][MXN];
int L, R;

int prt(int pos, int tg) {
    return ((pos - tg) & 1) ? -1 : 1;
}

void DP(int x) {
    int id = dist[x].sc;
    x++;
    debug(x, id);
    alive[id]--;
    L = 0;
    FOR(i, 0, id) L += alive[i];
    R = 0;
    FOR(i, id + 1, n) R += alive[i];
    FOR(i, 0, x + 1) {
        dpl[i][x - i] = INF;
        dpr[i][x - i] = INF;
    }
    dpl[x][0] = min(dpl[x][0], dpl[x - 1][0] + ((a[id] * prt(id, x - 1)) <= 0 ? L : INF));
    dpr[0][x] = min(dpr[0][x], dpr[0][x - 1] + ((a[id] * prt(id, n - x)) >= 0 ? R : INF));
    FOR(i, 1, x) {
        dpl[i][x - i] = min(dpl[i][x - i], min(dpl[i - 1][x - i], dpr[i - 1][x - i]) + ((a[id] * prt(id, i - 1)) <= 0 ? L : INF));
        dpr[i][x - i] = min(dpr[i][x - i], min(dpl[i][x - i - 1], dpr[i][x - i - 1]) + ((a[id] * prt(id, n - x + i)) >= 0 ? R : INF));
    }
}

void miku() {
    cin >> n;
    FOR(i, 0, n) {
        cin >> a[i];
        dist[i] = mp(abs(a[i]), i);
    }
    sort(dist, dist + n, greater<pii>());
    fill(alive, alive + n, 1);
    FOR(i, 0, n) {
        DP(i);
    }
    // FOR(i, 0, n + 1) {
    //     FOR(j, 0, n + 1 - i) cout << setw(3) << (dpl[i][j] == INF ? -1 : dpl[i][j]) << ' ';
    //     cout << endl;
    // }
    // cout << endl;
    // FOR(i, 0, n + 1) {
    //     FOR(j, 0, n + 1 - i) cout << setw(3) << (dpr[i][j] == INF ? -1 : dpr[i][j]) << ' ';
    //     cout << endl;
    // }
    // cout << endl;
    int ans = INF;
    FOR(i, 0, n + 1) ans = min(ans, dpl[i][n - i]);
    FOR(i, 0, n + 1) ans = min(ans, dpr[i][n - i]);
    cout << (ans >= INF ? -1 : ans) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message

Main.cpp: In function 'void DP(int)':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:35:5: note: in expansion of macro 'debug'
   35 |     debug(x, id);
      |     ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 28 ms 31720 KB Output is correct
4 Correct 27 ms 31564 KB Output is correct
5 Correct 23 ms 31472 KB Output is correct
6 Correct 31 ms 31568 KB Output is correct
7 Correct 28 ms 31448 KB Output is correct
8 Correct 48 ms 31448 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 27 ms 31468 KB Output is correct
12 Correct 23 ms 31580 KB Output is correct
13 Correct 36 ms 31572 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 28 ms 31720 KB Output is correct
4 Correct 27 ms 31564 KB Output is correct
5 Correct 23 ms 31472 KB Output is correct
6 Correct 31 ms 31568 KB Output is correct
7 Correct 28 ms 31448 KB Output is correct
8 Correct 48 ms 31448 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 27 ms 31468 KB Output is correct
12 Correct 23 ms 31580 KB Output is correct
13 Correct 36 ms 31572 KB Output is correct
14 Runtime error 3 ms 860 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -