QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#122878#1808. Efficient PartitioningScarlett_boyWA 1ms3492kbC++173.2kb2023-07-11 13:24:102023-07-11 13:24:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 13:24:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3492kb
  • [2023-07-11 13:24:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n;
const int mod = 1e9 + 7;

const ll Eps = 1e18, L = 1, R = 2e18;

struct Tree {
#define LOG 65
    int root, cnt, Mi, Ma;
    vector<int> ls, rs;
    vector<ll> MAX1, MAX2;

    Tree(int M = 0, ll Min = 1, ll Max = 2e18) : ls(M * LOG), rs(M * LOG), MAX1(M * LOG, -Eps), MAX2(M * LOG, -Eps) {
        root = 0, cnt = 0;
        Mi = Min, Ma = Max;
    }

    inline void pushup(int p) {
        MAX1[p] = max(MAX1[ls[p]], MAX1[rs[p]]);
        MAX2[p] = max(MAX2[ls[p]], MAX2[rs[p]]);
    }

    inline void New(int &p) {
        p = ++cnt;
//        MAX1[p] = MAX2[p] = -Eps;
    }

    inline void update(int &p, ll l, ll r, ll x, ll w1, ll w2) {
        if (!p) New(p);
        if (l == r) {
            MAX1[p] = max(MAX1[p], w1);
            MAX2[p] = max(MAX2[p], w2);
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) update(ls[p], l, mid, x, w1, w2);
        else update(rs[p], mid + 1, r, x, w1, w2);
        pushup(p);
    }

    inline void update(int x, ll w1, ll w2) { update(root, Mi, Ma, x, w1, w2); }

    inline ll query1(int p, ll l, ll r, ll x, ll y) {
        if (!p) return -Eps;
        if (x <= l && r <= y) return MAX1[p];
        ll ans = -Eps;
        int mid = l + r >> 1;
        if (x <= mid) ans = max(ans, query1(ls[p], l, mid, x, y));
        if (y > mid) ans = max(ans, query1(rs[p], mid + 1, r, x, y));
        return ans;
    }

    inline ll query1(ll l, ll r) { return query1(root, Mi, Ma, l, r); }

    inline ll query2(int p, ll l, ll r, ll x, ll y) {
        if (!p) return -Eps;
        if (x <= l && r <= y) return MAX2[p];
        ll ans = -Eps;
        int mid = l + r >> 1;
        if (x <= mid) ans = max(ans, query2(ls[p], l, mid, x, y));
        if (y > mid) ans = max(ans, query2(rs[p], mid + 1, r, x, y));
        return ans;
    }

    inline ll query2(ll l, ll r) { return query2(root, Mi, Ma, l, r); }
};


void solve() {
    cin >> n;
    vector<ll> a(n + 5), b(n + 5), c(n + 5), sum(n + 5);
    vector<ll> dp(n + 5, -Eps);
    Tree T(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    sum[0] = a[0];
    for (int i = 1; i < n; i++) sum[i] = a[i] + sum[i - 1];
    dp[0] = a[0] + b[0] + c[0];

    T.update(dp[0] - b[1] + sum[0] + Eps, dp[0], b[1] - sum[0]);
    for (int i = 1; i < n; i++) {
//        for (int j = 0; j < i; j++) {
//            dp[i] = max(dp[i], min(dp[j], b[j + 1] + c[i] + query(j + 1, i)));
//        }
        ll x = c[i] + sum[i] + Eps;
        dp[i] = max(T.query1(L, x), T.query2(x, R) + c[i] + sum[i]);
//        cout << T.query1(L, x) << " " << T.query2(x, R) + c[i] + sum[i] << " " << T.query2(x, R) << "\n";
        T.update(dp[i] - b[i + 1] + sum[i] + Eps, dp[i], b[i + 1] - sum[i]);
    }
    cout << dp[n - 1] << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
//    cin >> _;
    for (int o = 1; o <= _; o++) {
        //      cout << "Case #<<" << o << ": ";
        solve();
    }
    return 0;
}

/*

1
10 4
AABABBABAB
10 3 4 10 7 1 8 10 7 6

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

2
1 -1
-1 4
1 -2

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok answer is '3000000000'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3492kb

input:

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -72...

output:

-1485458360

result:

wrong answer expected '91174984', found '-1485458360'