oj.uz

답안 #544875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544875 2022-04-03T01:48:46 Z 4fecta Candies (JOI18_candies) C++17
8 / 100
 16 ms 7964 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 100005;

int n, a[MN], vis[MN], ans, take, pre[MN], nxt[MN], len[MN];

struct edge {
    int u, v, cost;
};

bool cmp(edge p, edge q) {
    return p.cost < q.cost;
}

int32_t main() {
    boost();

    cin >> n;
    n++;
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
        pre[i] = i - 1, nxt[i] = i + 1, len[i] = a[i] - a[i - 1];
    }
    priority_queue<edge, vector<edge>, decltype(&cmp)> q(cmp);
    for (int i = 1; i < n; i++) q.push({i, i + 1, a[i + 1] - a[i]});
    while (take < n / 2) {
        edge cur = q.top();
        q.pop();
        if (vis[cur.u] || vis[cur.v]) continue;
        vis[cur.u] = vis[cur.v] = 1;
        ans += cur.cost;
        nxt[pre[cur.u]] = nxt[cur.v];
        pre[nxt[cur.v]] = pre[cur.u];
        len[nxt[cur.v]] += len[cur.u] - len[cur.v];
        take++;
        if (pre[cur.u] > 0 && nxt[cur.v] <= n) q.push({pre[cur.u], nxt[cur.v], len[nxt[cur.v]]});
        printf("%lld\n", ans);
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 472 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 472 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 484 KB Output is correct
20 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 524 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 472 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 472 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 484 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Runtime error 16 ms 7964 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -