oj.uz

Submission #679480

# Submission time Handle Problem Language Result Execution time Memory
679480 2023-01-08T12:00:23 Z keta_tsimakuridze Two Dishes (JOI19_dishes) C++14
10 / 100
 10000 ms 34432 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7, inf = 1e18; // !
int lazy[4 * N][2], a[N][2], c[N][2], s[N][2], n[2];
vector<pii> x[N];
pii t[4 * N];
pii merge(pii x, pii y) {
    return (x.f < y.f ? y : x);
}
void push(int u, int l, int r) {
    if(lazy[u][0] != -inf) {
        t[u].f = lazy[u][0];
        if(l < r) {
            lazy[2 * u][1] = lazy[2 * u + 1][1] = 0;
            lazy[2 * u][0] = lazy[2 * u + 1][0] = lazy[u][0];
        }
        lazy[u][0] = -inf;
    }
    if(lazy[u][1] != 0) {
        t[u].f += lazy[u][1];
        if(l < r) {
            lazy[2 * u][1] += lazy[u][1];
            lazy[2 * u + 1][1] += lazy[u][1];
        }
        lazy[u][1] = 0;
    }
}
void upd(int u, int st, int en, int l, int r, int x, int T) {
    push(u, l, r);
    if(l > en || r < st) return;
    if(st <= l && r <= en) {
        lazy[u][T] = x;
        push(u, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, x, T); upd(2 * u + 1, st, en, mid + 1, r, x, T);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
pii get(int u, int st, int en, int l, int r) {
    push(u, l, r);
    if(l > en || r < st) return {-inf, 0};
    if(st <= l && r <= en) return t[u];
    int mid = (l + r) / 2;
    return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
void build(int u, int l, int r) {
    t[u].s = l; lazy[u][0] = -inf;
    if(l == r) return;
    build(2 * u, l, (l + r) / 2); build(2 * u + 1, (l + r)/ 2 + 1, r);
}
main(){
    int  m;
    cin >> n[0] >> n[1];
    for(int t = 0; t < 2; t++) {
        for(int i = 1; i <= n[t]; i++) {
            cin >> a[i][t] >> s[i][t] >> c[i][t];
            a[i][t] += a[i - 1][t];
        }
    }
    int ans = 0;
    for(int t = 0; t < 2; t++) {
        int R = n[t^1];
        for(int i = 1; i <= n[t]; i++) {

            int l = 0, r = n[t^1], R = -1;

            while(l <= r) {
                int mid = (l + r) / 2;
                if(a[i][t] + a[mid][t^1] <= s[i][t]) R = mid, l = mid + 1;
                else r = mid - 1;
            }
            if(!t) {
                // R tu aris i - s win mashin ver vigebt
                ++R;
                ans += c[i][t];
                //cout << i << " __ " << R << " " << a[i][t] << endl;
                x[i].push_back({R, -c[i][t]});
                continue;
            }
            ++R;
            if(R == n[0] + 1) {
                ans += c[i][t];
                continue;
            }
            // R tu aris i - s shemdeg mashin vigebt
            // i tu aris R - is win mashin vigebt

            x[R].push_back({i, c[i][t]});
        }
    }

    vector<int> dp(n[1] + 1);
    for(int i = 1; i <= n[0]; i++) {
        for(int j = 1; j <= n[1]; j++) dp[j] = max(dp[j], dp[j - 1]);
        sort(x[i].begin(), x[i].end());

        for(int k = 0; k < x[i].size(); k++) {
            for(int j = x[i][k].f; j <= n[1]; j++) dp[j] += x[i][k].s;
        }
    }
    int mn = -inf;
    for(int i = 0; i <= n[1]; i++) mn = max(mn, dp[i]);
    cout << ans + mn << "\n";
    return 0;
    build(1, 0, n[1]);
    for(int i = 1; i <= n[0]; i++) {

        sort(x[i].begin(), x[i].end());
        int R = n[1];
        // prefix max
        while(R >= 0) {
            pii x = get(1, 1, R, 0, n[1]);
            upd(1, x.s, R, 0, n[1], x.f, 0);
            R = x.s - 1;
        }
        int c = 0;
        for(int j = 0; j < x[i].size(); j++) {
            c = x[i][j].s;
            upd(1, x[i][j].f, n[1], 0, n[1], c, 1);
        }
    }

    cout << t[1].f + ans;

 }

Compilation message

dishes.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:67:13: warning: unused variable 'R' [-Wunused-variable]
   67 |         int R = n[t^1];
      |             ^
dishes.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int k = 0; k < x[i].size(); k++) {
      |                        ~~^~~~~~~~~~~~~
dishes.cpp:122:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(int j = 0; j < x[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~
dishes.cpp:57:10: warning: unused variable 'm' [-Wunused-variable]
   57 |     int  m;
      |          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10017 ms 26944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5032 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 22 ms 5336 KB Output is correct
18 Correct 22 ms 5332 KB Output is correct
19 Correct 22 ms 5272 KB Output is correct
20 Correct 20 ms 5332 KB Output is correct
21 Correct 21 ms 5280 KB Output is correct
22 Correct 23 ms 5292 KB Output is correct
23 Correct 21 ms 5284 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5032 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 22 ms 5336 KB Output is correct
18 Correct 22 ms 5332 KB Output is correct
19 Correct 22 ms 5272 KB Output is correct
20 Correct 20 ms 5332 KB Output is correct
21 Correct 21 ms 5280 KB Output is correct
22 Correct 23 ms 5292 KB Output is correct
23 Correct 21 ms 5284 KB Output is correct
24 Execution timed out 10067 ms 34432 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5032 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 22 ms 5336 KB Output is correct
18 Correct 22 ms 5332 KB Output is correct
19 Correct 22 ms 5272 KB Output is correct
20 Correct 20 ms 5332 KB Output is correct
21 Correct 21 ms 5280 KB Output is correct
22 Correct 23 ms 5292 KB Output is correct
23 Correct 21 ms 5284 KB Output is correct
24 Execution timed out 10067 ms 34432 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5032 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 22 ms 5336 KB Output is correct
18 Correct 22 ms 5332 KB Output is correct
19 Correct 22 ms 5272 KB Output is correct
20 Correct 20 ms 5332 KB Output is correct
21 Correct 21 ms 5280 KB Output is correct
22 Correct 23 ms 5292 KB Output is correct
23 Correct 21 ms 5284 KB Output is correct
24 Execution timed out 10067 ms 34432 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10017 ms 26944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10017 ms 26944 KB Time limit exceeded
2 Halted 0 ms 0 KB -