oj.uz

답안 #336453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336453 2020-12-15T10:51:20 Z ncduy0303 Feast (NOI19_feast) C++17
0 / 100
 234 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

struct block {
    int l, r;
    ll sum;
};

void solve() {
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    deque<block> dq;
    for (int i = 0, num = 0; i < n;) {
        dq.push_back({-1, -1, 0});
        int j = i;
        while (j < n && a[j] * a[i] >= 0) dq.back().sum += a[j++];
        i = j;
    }
    if (dq.size() && dq.front().sum <= 0) dq.pop_front();
    if (dq.size() && dq.back().sum <= 0) dq.pop_back();
    if (dq.size()) dq.front().l = dq.back().r = -1;
    n = dq.size();
    for (int i = 0; i < n; i++) {
        if (i > 0) dq[i].l = i - 1;
        if (i < n - 1) dq[i].r = i + 1;
    }
    priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
    for (int i = 0; i < n; i++) pq.push({abs(dq[i].sum), i});
    vector<bool> vis(n);
    int cnt = n / 2 + 1; // no. of positive values in deque
    for (auto cur : dq) cerr << cur.sum << " ";
    cerr << "\n";
    while (cnt > m) {
        auto [v, i] = pq.top(); pq.pop();
        if (vis[i]) continue;
        vis[i] = true;
        cnt--;

        if (dq[i].l == -1) {
            vis[dq[i].r] = true;
            dq[dq[dq[i].r].r].l = -1;
        }
        else if (dq[i].r == -1) {
            vis[dq[i].l] = true;
            dq[dq[dq[i].l].l].r = -1;
        }
        else {
            vis[dq[i].l] = vis[dq[i].r] = true;
            dq[i].sum += dq[dq[i].l].sum + dq[dq[i].r].sum;
            if (dq[dq[i].l].l != -1) dq[dq[dq[i].l].l].r = i;
            if (dq[dq[i].r].r != -1) dq[dq[dq[i].r].r].l = i;
            dq[i].l = dq[dq[i].l].l;
            dq[i].r = dq[dq[i].r].r;
            vis[i] = false;
            pq.push({abs(dq[i].sum), i});
        }

        for (auto cur : dq) cerr << cur.sum << " ";
        cerr << "\n";
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] || dq[i].sum <= 0) continue;
        ans += dq[i].sum;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Compilation message

feast.cpp: In function 'void solve()':
feast.cpp:23:21: warning: unused variable 'num' [-Wunused-variable]
   23 |     for (int i = 0, num = 0; i < n;) {
      |                     ^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 231 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2540 KB Output is correct
2 Runtime error 228 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 234 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 201 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 201 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 201 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 231 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -