oj.uz

Submission #375831

# Submission time Handle Problem Language Result Execution time Memory
375831 2021-03-10T03:50:45 Z 2qbingxuan Two Dishes (JOI19_dishes) C++14
10 / 100
 10000 ms 27628 KB 
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\n")));
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local

using namespace std;
const int maxn = 200025;


struct Item {
    int t;
    int64_t ed;
    int val;
} v[maxn], u[maxn];
int64_t sumv[maxn], sumu[maxn];
int posv[maxn], posu[maxn];
int64_t dp[maxn], dif[maxn];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i].t >> v[i].ed >> v[i].val;
    for (int i = 1; i <= m; i++)
        cin >> u[i].t >> u[i].ed >> u[i].val;

    for (int i = 1; i <= n; i++)
        sumv[i] = sumv[i-1] + v[i].t;
    for (int i = 1; i <= m; i++)
        sumu[i] = sumu[i-1] + u[i].t;

    for (int i = 1; i <= n; i++)
        posv[i] = upper_bound(sumu, sumu+m+1, v[i].ed - sumv[i]) - sumu - 1;
    for (int i = 1; i <= m; i++)
        posu[i] = upper_bound(sumv, sumv+n+1, u[i].ed - sumu[i]) - sumv - 1;

    for (int j = 1; j <= m; j++) dp[j] = dp[j-1] + (posu[j] >= 0 ? u[j].val : 0);
    for (int j = 1; j <= m; j++) dif[j] = (posu[j] >= 0 ? u[j].val : 0);

    /*
    cerr << "posu:\t";
    cerr << 0 << ' ';
    for (int i = 1; i <= m; i++) cerr << posu[i] << ' ';
    cerr << '\n';
    cerr << "u.val:\t";
    cerr << 0 << ' ';
    for (int i = 1; i <= m; i++) cerr << u[i].val << ' ';
    cerr << '\n';
    */

    function<void(int,int,int64_t)> update = [&](int i, int j, int64_t val) {
        if (val == 0 || j == m+1) return;
        dif[j] -= val;
        int64_t c = max<int64_t>(0, (j != 0 && i <= posu[j] ? u[j].val : 0) - dif[j]);
        dif[j] += c;
        update(i, j+1, c);
    };
    for (int i = 1; i <= n; i++) {
        dif[0] += v[i].val;
        update(i, posv[i]+1, v[i].val);

        /*
        for (int j = 0; j <= posv[i]; j++) dp[j] += v[i].val;
        for (int j = 1; j <= m; j++) dp[j] = max(dp[j], dp[j-1] + (i <= posu[j] ? u[j].val : 0));

        cerr << posv[i] << ';' << v[i].val << ";\t";
        for (int j = 0; j <= m; j++) cerr << (dp[j] - (j ? dp[j-1] : 0)) << ' ';
        cerr << '\n';
        */
    }
    debug(dp[m]);
    int64_t sum = 0;
    for (int i = 0; i <= m; i++) sum += dif[i];
    cout << sum << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 18540 KB Output is correct
2 Execution timed out 10080 ms 20464 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 45 ms 748 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 4 ms 896 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 3 ms 620 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 45 ms 748 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 4 ms 896 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 3 ms 620 KB Output is correct
24 Execution timed out 10068 ms 27628 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 45 ms 748 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 4 ms 896 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 3 ms 620 KB Output is correct
24 Execution timed out 10068 ms 27628 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 45 ms 748 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 4 ms 896 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 6 ms 748 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 3 ms 620 KB Output is correct
24 Execution timed out 10068 ms 27628 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 18540 KB Output is correct
2 Execution timed out 10080 ms 20464 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 18540 KB Output is correct
2 Execution timed out 10080 ms 20464 KB Time limit exceeded
3 Halted 0 ms 0 KB -