oj.uz

Submission #789617

# Submission time Handle Problem Language Result Execution time Memory
789617 2023-07-21T14:54:21 Z someone Two Dishes (JOI19_dishes) C++14
5 / 100
 490 ms 72556 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Point {
    int x, y, val;
};

const int M = 1 << 20, N = 2 * M, T = 12, INF = 1e18 + 42;

int maxi[N], tag[N];

void applyOp(int i, int add) {
    tag[i] += add;
    maxi[i] += add;
}

void propage(int i) {
    applyOp(i*2, tag[i]);
    applyOp(i*2+1, tag[i]);
    tag[i] = 0;
}

int update(int i, int deb, int fin, int l, int r, int add) {
    if(r <= deb || fin <= l)
        return -INF;
    if(l <= deb && fin <= r) {
        applyOp(i, add);
        return maxi[i];
    }
    propage(i);
    int mid = ((deb + fin) >> 1),
        ans = max(update(i*2, deb, mid, l, r, add),
                  update(i*2+1, mid, fin, l, r, add));
    maxi[i] = max(maxi[i*2], maxi[i*2+1]);
    return ans;
}

vector<Point> point;
int score = 0, ans = 0, sz[2], a[2][M], t[2][M], pt[2][M], pos[2][M], dp[T][T];

void solve() {
    score = ans = 0;
    point.clear();
    for(int i = 0; i < N; i++)
        tag[i] = 0, maxi[i] = -INF;
    update(1, 0, M, M-1, M, INF);
    for(int i = 0; i < 2; i++)
        for(int j = 1; j <= sz[i]; j++)
            a[i][j] += a[i][j-1];
    a[0][sz[0]+1] = a[1][sz[1]+1] = INF;
/*
    for(int i = 0; i <= sz[0]; i++)
        for(int j = 0; j <= sz[1]; j++)
            dp[i][j] = -INF;
    dp[0][0] = 0;
    for(int i = 0; i <= sz[0]; i++)
        for(int j = 0; j <= sz[1]; j++) {
            if(a[0][i+1] + a[1][j] <= t[0][i+1]) {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + pt[0][i+1]);
            } else {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            }
            if(a[0][i] + a[1][j+1] <= t[1][j+1]) {
                dp[i][j+1] = max(dp[i][j+1], dp[i][j] + pt[1][j+1]);
            } else {
                dp[i][j+1] = max(dp[i][j+1], dp[i][j]);
            }
        }*/

    for(int i = 0; i < 2; i++)
        for(int j = 1; j <= sz[i]; j++)
            pos[i][j] = (int)(upper_bound(a[1-i], a[1-i] + sz[1-i] + 1, t[i][j] - a[i][j]) - a[1-i]) - 1;

    for(int j = 0; j <= sz[0]; j++)
        if(pos[0][j] != -1)
            point.push_back({j, pos[0][j], pt[0][j]});
    for(int j = 1; j <= sz[1]; j++) {
        if(pos[1][j] != -1) {
            score += pt[1][j];
            point.push_back({pos[1][j]+1, j-1, -pt[1][j]});
        }
    }

    sort(point.begin(), point.end(),
    [](Point p1, Point p2) {
        if(p1.x == p2.x) {
            if(p1.y == p2.y)
                return p1.val > p2.val;
            return p1.y > p2.y;
        }
        return p1.x > p2.x;
    });

    for(Point p : point) {/*
        cout << p.x << ' ' << p.y << ' ' << p.val << '\n';
        for(int j = 0; j <= 10; j++) {
            int val = update(1, 0, M, j, j+1, 0);
            if(val == -INF) {
                cout << "- ";
            } else {
                cout << val << ' ';
            }
        }
        cout << '\n';*/
        int val = update(1, 0, M, p.y, M, 0);
        if(p.x == 0 && p.y == 0)
            ans = val;
        int pre = update(1, 0, M, p.y, p.y+1, 0);
        update(1, 0, M, p.y, p.y+1, val - pre);
        update(1, 0, M, 0, p.y+1, p.val);
    }
    cout << ans + score << '\n';
    /*
    if(dp[sz[0]][sz[1]] != ans + score) {
        cout << "Differ\n";
        cout << dp[sz[0]][sz[1]] << ' ' << ans + score << '\n';
        cout << sz[0] << ' ' << sz[1] << '\n';
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= sz[i]; j++)
                cout << a[i][j] << ' ' << t[i][j] << ' ' << pt[i][j] << '\n';
    }*/
}

int getRandom() {
    return (rand() % 10) + 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> sz[0] >> sz[1];
    for(int i = 0; i < 2; i++)
        for(int j = 1; j <= sz[i]; j++)
            cin >> a[i][j] >> t[i][j] >> pt[i][j];
    solve();
    /*
    for(int x = 0; x < 1000; x++) {
        srand(time(0) + x);
        sz[0] = sz[1] = 1;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= sz[i]; j++) {
                a[i][j] = getRandom();
                t[i][j] = getRandom();
                pt[i][j] = getRandom();
            }
        solve();
    }*/
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 59304 KB Output is correct
2 Correct 490 ms 71684 KB Output is correct
3 Correct 460 ms 71520 KB Output is correct
4 Correct 340 ms 65596 KB Output is correct
5 Correct 11 ms 33108 KB Output is correct
6 Correct 462 ms 70968 KB Output is correct
7 Correct 227 ms 52540 KB Output is correct
8 Correct 241 ms 52692 KB Output is correct
9 Correct 442 ms 72556 KB Output is correct
10 Correct 471 ms 65516 KB Output is correct
11 Correct 412 ms 65988 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33108 KB Output is correct
2 Correct 11 ms 33108 KB Output is correct
3 Correct 10 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33160 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 14 ms 33192 KB Output is correct
10 Incorrect 14 ms 33108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33108 KB Output is correct
2 Correct 11 ms 33108 KB Output is correct
3 Correct 10 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33160 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 14 ms 33192 KB Output is correct
10 Incorrect 14 ms 33108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33108 KB Output is correct
2 Correct 11 ms 33108 KB Output is correct
3 Correct 10 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33160 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 14 ms 33192 KB Output is correct
10 Incorrect 14 ms 33108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33108 KB Output is correct
2 Correct 11 ms 33108 KB Output is correct
3 Correct 10 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33160 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 14 ms 33192 KB Output is correct
10 Incorrect 14 ms 33108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33108 KB Output is correct
2 Correct 11 ms 33108 KB Output is correct
3 Correct 10 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33160 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 14 ms 33192 KB Output is correct
10 Incorrect 14 ms 33108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 59304 KB Output is correct
2 Correct 490 ms 71684 KB Output is correct
3 Correct 460 ms 71520 KB Output is correct
4 Correct 340 ms 65596 KB Output is correct
5 Correct 11 ms 33108 KB Output is correct
6 Correct 462 ms 70968 KB Output is correct
7 Correct 227 ms 52540 KB Output is correct
8 Correct 241 ms 52692 KB Output is correct
9 Correct 442 ms 72556 KB Output is correct
10 Correct 471 ms 65516 KB Output is correct
11 Correct 412 ms 65988 KB Output is correct
12 Correct 10 ms 33108 KB Output is correct
13 Correct 11 ms 33108 KB Output is correct
14 Correct 10 ms 33108 KB Output is correct
15 Correct 14 ms 33108 KB Output is correct
16 Correct 15 ms 33108 KB Output is correct
17 Correct 15 ms 33160 KB Output is correct
18 Correct 14 ms 33108 KB Output is correct
19 Correct 14 ms 33108 KB Output is correct
20 Correct 14 ms 33192 KB Output is correct
21 Incorrect 14 ms 33108 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 59304 KB Output is correct
2 Correct 490 ms 71684 KB Output is correct
3 Correct 460 ms 71520 KB Output is correct
4 Correct 340 ms 65596 KB Output is correct
5 Correct 11 ms 33108 KB Output is correct
6 Correct 462 ms 70968 KB Output is correct
7 Correct 227 ms 52540 KB Output is correct
8 Correct 241 ms 52692 KB Output is correct
9 Correct 442 ms 72556 KB Output is correct
10 Correct 471 ms 65516 KB Output is correct
11 Correct 412 ms 65988 KB Output is correct
12 Correct 10 ms 33108 KB Output is correct
13 Correct 11 ms 33108 KB Output is correct
14 Correct 10 ms 33108 KB Output is correct
15 Correct 14 ms 33108 KB Output is correct
16 Correct 15 ms 33108 KB Output is correct
17 Correct 15 ms 33160 KB Output is correct
18 Correct 14 ms 33108 KB Output is correct
19 Correct 14 ms 33108 KB Output is correct
20 Correct 14 ms 33192 KB Output is correct
21 Incorrect 14 ms 33108 KB Output isn't correct
22 Halted 0 ms 0 KB -