oj.uz

Submission #789637

# Submission time Handle Problem Language Result Execution time Memory
789637 2023-07-21T15:31:48 Z someone Two Dishes (JOI19_dishes) C++14
10 / 100
 1120 ms 357976 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 = 2042, 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 < 1000000; x++) {
        srand(time(0) + x);
        sz[0] = sz[1] = 18;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= sz[i]; j++) {
                a[i][j] = (rand() % 10000) + 1;
                t[i][j] = (rand() % 200000) + 1;
                pt[i][j] = (rand() % 20000000) - 10000000;
            }
        solve();
    }*/
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1120 ms 346804 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 36 ms 57892 KB Output is correct
2 Correct 48 ms 57776 KB Output is correct
3 Correct 32 ms 57852 KB Output is correct
4 Correct 31 ms 57868 KB Output is correct
5 Correct 30 ms 57852 KB Output is correct
6 Correct 31 ms 57760 KB Output is correct
7 Correct 36 ms 57892 KB Output is correct
8 Correct 31 ms 57820 KB Output is correct
9 Correct 31 ms 57876 KB Output is correct
10 Correct 32 ms 57852 KB Output is correct
11 Correct 30 ms 57804 KB Output is correct
12 Correct 36 ms 57900 KB Output is correct
13 Correct 31 ms 57812 KB Output is correct
14 Correct 31 ms 57864 KB Output is correct
15 Correct 31 ms 57844 KB Output is correct
16 Correct 31 ms 57804 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 57892 KB Output is correct
2 Correct 48 ms 57776 KB Output is correct
3 Correct 32 ms 57852 KB Output is correct
4 Correct 31 ms 57868 KB Output is correct
5 Correct 30 ms 57852 KB Output is correct
6 Correct 31 ms 57760 KB Output is correct
7 Correct 36 ms 57892 KB Output is correct
8 Correct 31 ms 57820 KB Output is correct
9 Correct 31 ms 57876 KB Output is correct
10 Correct 32 ms 57852 KB Output is correct
11 Correct 30 ms 57804 KB Output is correct
12 Correct 36 ms 57900 KB Output is correct
13 Correct 31 ms 57812 KB Output is correct
14 Correct 31 ms 57864 KB Output is correct
15 Correct 31 ms 57844 KB Output is correct
16 Correct 31 ms 57804 KB Output is correct
17 Correct 57 ms 90076 KB Output is correct
18 Correct 52 ms 90188 KB Output is correct
19 Correct 55 ms 90204 KB Output is correct
20 Correct 54 ms 90060 KB Output is correct
21 Correct 54 ms 89016 KB Output is correct
22 Correct 54 ms 90188 KB Output is correct
23 Correct 56 ms 90184 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 57892 KB Output is correct
2 Correct 48 ms 57776 KB Output is correct
3 Correct 32 ms 57852 KB Output is correct
4 Correct 31 ms 57868 KB Output is correct
5 Correct 30 ms 57852 KB Output is correct
6 Correct 31 ms 57760 KB Output is correct
7 Correct 36 ms 57892 KB Output is correct
8 Correct 31 ms 57820 KB Output is correct
9 Correct 31 ms 57876 KB Output is correct
10 Correct 32 ms 57852 KB Output is correct
11 Correct 30 ms 57804 KB Output is correct
12 Correct 36 ms 57900 KB Output is correct
13 Correct 31 ms 57812 KB Output is correct
14 Correct 31 ms 57864 KB Output is correct
15 Correct 31 ms 57844 KB Output is correct
16 Correct 31 ms 57804 KB Output is correct
17 Correct 57 ms 90076 KB Output is correct
18 Correct 52 ms 90188 KB Output is correct
19 Correct 55 ms 90204 KB Output is correct
20 Correct 54 ms 90060 KB Output is correct
21 Correct 54 ms 89016 KB Output is correct
22 Correct 54 ms 90188 KB Output is correct
23 Correct 56 ms 90184 KB Output is correct
24 Runtime error 1077 ms 357976 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 57892 KB Output is correct
2 Correct 48 ms 57776 KB Output is correct
3 Correct 32 ms 57852 KB Output is correct
4 Correct 31 ms 57868 KB Output is correct
5 Correct 30 ms 57852 KB Output is correct
6 Correct 31 ms 57760 KB Output is correct
7 Correct 36 ms 57892 KB Output is correct
8 Correct 31 ms 57820 KB Output is correct
9 Correct 31 ms 57876 KB Output is correct
10 Correct 32 ms 57852 KB Output is correct
11 Correct 30 ms 57804 KB Output is correct
12 Correct 36 ms 57900 KB Output is correct
13 Correct 31 ms 57812 KB Output is correct
14 Correct 31 ms 57864 KB Output is correct
15 Correct 31 ms 57844 KB Output is correct
16 Correct 31 ms 57804 KB Output is correct
17 Correct 57 ms 90076 KB Output is correct
18 Correct 52 ms 90188 KB Output is correct
19 Correct 55 ms 90204 KB Output is correct
20 Correct 54 ms 90060 KB Output is correct
21 Correct 54 ms 89016 KB Output is correct
22 Correct 54 ms 90188 KB Output is correct
23 Correct 56 ms 90184 KB Output is correct
24 Runtime error 1077 ms 357976 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 57892 KB Output is correct
2 Correct 48 ms 57776 KB Output is correct
3 Correct 32 ms 57852 KB Output is correct
4 Correct 31 ms 57868 KB Output is correct
5 Correct 30 ms 57852 KB Output is correct
6 Correct 31 ms 57760 KB Output is correct
7 Correct 36 ms 57892 KB Output is correct
8 Correct 31 ms 57820 KB Output is correct
9 Correct 31 ms 57876 KB Output is correct
10 Correct 32 ms 57852 KB Output is correct
11 Correct 30 ms 57804 KB Output is correct
12 Correct 36 ms 57900 KB Output is correct
13 Correct 31 ms 57812 KB Output is correct
14 Correct 31 ms 57864 KB Output is correct
15 Correct 31 ms 57844 KB Output is correct
16 Correct 31 ms 57804 KB Output is correct
17 Correct 57 ms 90076 KB Output is correct
18 Correct 52 ms 90188 KB Output is correct
19 Correct 55 ms 90204 KB Output is correct
20 Correct 54 ms 90060 KB Output is correct
21 Correct 54 ms 89016 KB Output is correct
22 Correct 54 ms 90188 KB Output is correct
23 Correct 56 ms 90184 KB Output is correct
24 Runtime error 1077 ms 357976 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1120 ms 346804 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 1120 ms 346804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -