oj.uz

Submission #789632

# Submission time Handle Problem Language Result Execution time Memory
789632 2023-07-21T15:25:14 Z someone Two Dishes (JOI19_dishes) C++14
0 / 100
 506 ms 104316 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 -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, value[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';
/*
    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 < 1000; x++) {
        srand(time(0) + x);
        sz[0] = sz[1] = 10;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= sz[i]; j++) {
                a[i][j] = (rand() % 10) + 1;
                t[i][j] = (rand() % 100) + 1;
                pt[i][j] = (rand() % 20) - 10;
            }
        solve();
    }*/
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 102572 KB Output is correct
2 Correct 490 ms 104316 KB Output is correct
3 Correct 289 ms 99320 KB Output is correct
4 Correct 381 ms 97752 KB Output is correct
5 Correct 33 ms 74240 KB Output is correct
6 Correct 472 ms 103152 KB Output is correct
7 Incorrect 90 ms 81740 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74160 KB Output is correct
2 Correct 33 ms 74196 KB Output is correct
3 Correct 32 ms 74216 KB Output is correct
4 Correct 36 ms 74188 KB Output is correct
5 Correct 34 ms 74196 KB Output is correct
6 Correct 34 ms 74188 KB Output is correct
7 Correct 33 ms 74136 KB Output is correct
8 Correct 34 ms 74204 KB Output is correct
9 Correct 34 ms 74236 KB Output is correct
10 Correct 36 ms 74244 KB Output is correct
11 Correct 34 ms 74120 KB Output is correct
12 Correct 34 ms 74188 KB Output is correct
13 Correct 35 ms 74200 KB Output is correct
14 Correct 34 ms 74184 KB Output is correct
15 Incorrect 37 ms 74192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74160 KB Output is correct
2 Correct 33 ms 74196 KB Output is correct
3 Correct 32 ms 74216 KB Output is correct
4 Correct 36 ms 74188 KB Output is correct
5 Correct 34 ms 74196 KB Output is correct
6 Correct 34 ms 74188 KB Output is correct
7 Correct 33 ms 74136 KB Output is correct
8 Correct 34 ms 74204 KB Output is correct
9 Correct 34 ms 74236 KB Output is correct
10 Correct 36 ms 74244 KB Output is correct
11 Correct 34 ms 74120 KB Output is correct
12 Correct 34 ms 74188 KB Output is correct
13 Correct 35 ms 74200 KB Output is correct
14 Correct 34 ms 74184 KB Output is correct
15 Incorrect 37 ms 74192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74160 KB Output is correct
2 Correct 33 ms 74196 KB Output is correct
3 Correct 32 ms 74216 KB Output is correct
4 Correct 36 ms 74188 KB Output is correct
5 Correct 34 ms 74196 KB Output is correct
6 Correct 34 ms 74188 KB Output is correct
7 Correct 33 ms 74136 KB Output is correct
8 Correct 34 ms 74204 KB Output is correct
9 Correct 34 ms 74236 KB Output is correct
10 Correct 36 ms 74244 KB Output is correct
11 Correct 34 ms 74120 KB Output is correct
12 Correct 34 ms 74188 KB Output is correct
13 Correct 35 ms 74200 KB Output is correct
14 Correct 34 ms 74184 KB Output is correct
15 Incorrect 37 ms 74192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74160 KB Output is correct
2 Correct 33 ms 74196 KB Output is correct
3 Correct 32 ms 74216 KB Output is correct
4 Correct 36 ms 74188 KB Output is correct
5 Correct 34 ms 74196 KB Output is correct
6 Correct 34 ms 74188 KB Output is correct
7 Correct 33 ms 74136 KB Output is correct
8 Correct 34 ms 74204 KB Output is correct
9 Correct 34 ms 74236 KB Output is correct
10 Correct 36 ms 74244 KB Output is correct
11 Correct 34 ms 74120 KB Output is correct
12 Correct 34 ms 74188 KB Output is correct
13 Correct 35 ms 74200 KB Output is correct
14 Correct 34 ms 74184 KB Output is correct
15 Incorrect 37 ms 74192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 74160 KB Output is correct
2 Correct 33 ms 74196 KB Output is correct
3 Correct 32 ms 74216 KB Output is correct
4 Correct 36 ms 74188 KB Output is correct
5 Correct 34 ms 74196 KB Output is correct
6 Correct 34 ms 74188 KB Output is correct
7 Correct 33 ms 74136 KB Output is correct
8 Correct 34 ms 74204 KB Output is correct
9 Correct 34 ms 74236 KB Output is correct
10 Correct 36 ms 74244 KB Output is correct
11 Correct 34 ms 74120 KB Output is correct
12 Correct 34 ms 74188 KB Output is correct
13 Correct 35 ms 74200 KB Output is correct
14 Correct 34 ms 74184 KB Output is correct
15 Incorrect 37 ms 74192 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 102572 KB Output is correct
2 Correct 490 ms 104316 KB Output is correct
3 Correct 289 ms 99320 KB Output is correct
4 Correct 381 ms 97752 KB Output is correct
5 Correct 33 ms 74240 KB Output is correct
6 Correct 472 ms 103152 KB Output is correct
7 Incorrect 90 ms 81740 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 102572 KB Output is correct
2 Correct 490 ms 104316 KB Output is correct
3 Correct 289 ms 99320 KB Output is correct
4 Correct 381 ms 97752 KB Output is correct
5 Correct 33 ms 74240 KB Output is correct
6 Correct 472 ms 103152 KB Output is correct
7 Incorrect 90 ms 81740 KB Output isn't correct
8 Halted 0 ms 0 KB -