oj.uz

Submission #789605

# Submission time Handle Problem Language Result Execution time Memory
789605 2023-07-21T14:34:20 Z someone Two Dishes (JOI19_dishes) C++14
3 / 100
 1 ms 596 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int M = 1 << 4, 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[N][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];
    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]);
            }
        }
    cout << dp[sz[0]][sz[1]] << '\n';/*

    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)
            return p1.y < p2.y;
        return p1.x > p2.x;
    });

    for(Point p : point) {
        int val = update(1, 0, M, p.y, M, 0);
        ans = max(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';*/
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -