oj.uz

Submission #789641

# Submission time Handle Problem Language Result Execution time Memory
789641 2023-07-21T15:37:20 Z someone Two Dishes (JOI19_dishes) C++14
0 / 100
 497 ms 89900 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 = 35, 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 -2*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<int> lig[M];
vector<Point> point;
int score = 0, ans = 0, sz[2], value[N], 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 < M; i++)
        lig[i].clear();

    for(int i = 0; i < N; i++)
        tag[i] = 0, maxi[i] = -INF;
    update(1, 0, M, sz[0], sz[0]+1, 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];
            if(pos[1][j] != sz[0])
                point.push_back({pos[1][j]+1, j-1, -pt[1][j]});
        }
    }

    for(int i = 0; i < (int)point.size(); i++)
        lig[point[i].x].push_back(i);
/*
    for(Point p : point)
        cout << p.x << ' ' << p.y << ' ' << p.val << '\n';
    cout << '\n' << '\n';*/
    for(int x = sz[0]; x >= 0; x--) {
        for(int id : lig[x]) {
            Point p = point[id];
            value[id] = update(1, 0, M, p.y, sz[0]+1, 0);
            if(p.x == 0 && p.y == 0)
                ans = value[id];
        }
        for(int id : lig[x]) {
            Point p = point[id];
            int pre = update(1, 0, M, p.y, p.y+1, 0);
            update(1, 0, M, p.y, p.y+1, value[id] - pre);
        }
        for(int id : lig[x]) {
            Point p = point[id];
            update(1, 0, M, 0, p.y+1, p.val);
        }/*
        for(int i = 0; i <= sz[0]; i++)
            cout << update(1, 0, M, i, i+1, 0) << ' ';
        cout << '\n' << '\n';*/
    }/*
    cout << '\n';
    cout << ans << ' ' << score << '\n';*/
    cout << ans + score << '\n';
    //cout << dp[sz[0]][sz[1]] << '\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';
    }*/
}

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 < 100000; x++) {
        srand(time(0) + x);
        sz[0] = sz[1] = 30;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= sz[i]; j++) {
                a[i][j] = (rand() % 1000000000) + 1;
                t[i][j] = (rand() % 20000000000) + 1;
                pt[i][j] = (rand() % 2000000000) - 1000000000;
            }
        solve();
    }*/
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 89732 KB Output is correct
2 Correct 491 ms 89900 KB Output is correct
3 Correct 293 ms 83400 KB Output is correct
4 Correct 368 ms 82360 KB Output is correct
5 Correct 22 ms 57812 KB Output is correct
6 Correct 451 ms 88264 KB Output is correct
7 Incorrect 73 ms 64588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57744 KB Output is correct
2 Correct 23 ms 57816 KB Output is correct
3 Correct 23 ms 57828 KB Output is correct
4 Correct 22 ms 57784 KB Output is correct
5 Correct 22 ms 57860 KB Output is correct
6 Correct 22 ms 57728 KB Output is correct
7 Correct 22 ms 57804 KB Output is correct
8 Correct 22 ms 57780 KB Output is correct
9 Correct 22 ms 57812 KB Output is correct
10 Correct 23 ms 57852 KB Output is correct
11 Correct 26 ms 57820 KB Output is correct
12 Correct 22 ms 57784 KB Output is correct
13 Correct 22 ms 57780 KB Output is correct
14 Correct 22 ms 57740 KB Output is correct
15 Incorrect 22 ms 57720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57744 KB Output is correct
2 Correct 23 ms 57816 KB Output is correct
3 Correct 23 ms 57828 KB Output is correct
4 Correct 22 ms 57784 KB Output is correct
5 Correct 22 ms 57860 KB Output is correct
6 Correct 22 ms 57728 KB Output is correct
7 Correct 22 ms 57804 KB Output is correct
8 Correct 22 ms 57780 KB Output is correct
9 Correct 22 ms 57812 KB Output is correct
10 Correct 23 ms 57852 KB Output is correct
11 Correct 26 ms 57820 KB Output is correct
12 Correct 22 ms 57784 KB Output is correct
13 Correct 22 ms 57780 KB Output is correct
14 Correct 22 ms 57740 KB Output is correct
15 Incorrect 22 ms 57720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57744 KB Output is correct
2 Correct 23 ms 57816 KB Output is correct
3 Correct 23 ms 57828 KB Output is correct
4 Correct 22 ms 57784 KB Output is correct
5 Correct 22 ms 57860 KB Output is correct
6 Correct 22 ms 57728 KB Output is correct
7 Correct 22 ms 57804 KB Output is correct
8 Correct 22 ms 57780 KB Output is correct
9 Correct 22 ms 57812 KB Output is correct
10 Correct 23 ms 57852 KB Output is correct
11 Correct 26 ms 57820 KB Output is correct
12 Correct 22 ms 57784 KB Output is correct
13 Correct 22 ms 57780 KB Output is correct
14 Correct 22 ms 57740 KB Output is correct
15 Incorrect 22 ms 57720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57744 KB Output is correct
2 Correct 23 ms 57816 KB Output is correct
3 Correct 23 ms 57828 KB Output is correct
4 Correct 22 ms 57784 KB Output is correct
5 Correct 22 ms 57860 KB Output is correct
6 Correct 22 ms 57728 KB Output is correct
7 Correct 22 ms 57804 KB Output is correct
8 Correct 22 ms 57780 KB Output is correct
9 Correct 22 ms 57812 KB Output is correct
10 Correct 23 ms 57852 KB Output is correct
11 Correct 26 ms 57820 KB Output is correct
12 Correct 22 ms 57784 KB Output is correct
13 Correct 22 ms 57780 KB Output is correct
14 Correct 22 ms 57740 KB Output is correct
15 Incorrect 22 ms 57720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 57744 KB Output is correct
2 Correct 23 ms 57816 KB Output is correct
3 Correct 23 ms 57828 KB Output is correct
4 Correct 22 ms 57784 KB Output is correct
5 Correct 22 ms 57860 KB Output is correct
6 Correct 22 ms 57728 KB Output is correct
7 Correct 22 ms 57804 KB Output is correct
8 Correct 22 ms 57780 KB Output is correct
9 Correct 22 ms 57812 KB Output is correct
10 Correct 23 ms 57852 KB Output is correct
11 Correct 26 ms 57820 KB Output is correct
12 Correct 22 ms 57784 KB Output is correct
13 Correct 22 ms 57780 KB Output is correct
14 Correct 22 ms 57740 KB Output is correct
15 Incorrect 22 ms 57720 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 89732 KB Output is correct
2 Correct 491 ms 89900 KB Output is correct
3 Correct 293 ms 83400 KB Output is correct
4 Correct 368 ms 82360 KB Output is correct
5 Correct 22 ms 57812 KB Output is correct
6 Correct 451 ms 88264 KB Output is correct
7 Incorrect 73 ms 64588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 89732 KB Output is correct
2 Correct 491 ms 89900 KB Output is correct
3 Correct 293 ms 83400 KB Output is correct
4 Correct 368 ms 82360 KB Output is correct
5 Correct 22 ms 57812 KB Output is correct
6 Correct 451 ms 88264 KB Output is correct
7 Incorrect 73 ms 64588 KB Output isn't correct
8 Halted 0 ms 0 KB -