답안 #563878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563878	2022-05-18T07:56:21 Z	maomao90	Two Dishes (JOI19_dishes)	C++17	15 / 100	166 ms	32048 KB

dishes

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 1000005;

int n, m;
ll a[MAXN], s[MAXN], p[MAXN], c[MAXN];
ll b[MAXN], t[MAXN], q[MAXN], d[MAXN];
ll ans;

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> m;
    REP (i, 1, n + 1) {
        cin >> a[i] >> s[i] >> p[i];
        c[i] = a[i] + c[i - 1];
    }
    ll sm = 0, res = 0;
    REP (i, 1, m + 1) {
        cin >> b[i] >> t[i] >> q[i];
        d[i] = b[i] + d[i - 1];
        sm += b[i];
        res += q[i];
    }
    ans = -LINF;
    if (n <= 2000 && m <= 2000) {
        vector<vll> dp(n + 5, vll(m + 5, -LINF));
        REP (i, 0, n + 1) {
            REP (j, 0, m + 1) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 0;
                }
                if (i) {
                    mxto(dp[i][j], dp[i - 1][j] + p[i] * (d[j] <= s[i] - c[i]));
                }
                if (j) {
                    mxto(dp[i][j], dp[i][j - 1] + q[j] * (c[i] <= t[j] - d[j]));
                }
            }
        }
        ans = dp[n][m];
    } else {
        int j = m;
        ll gt = t[1];
        REP (i, 0, n + 1) {
            sm += a[i];
            res += p[i];
            while (j > 0 && sm > gt) {
                sm -= b[j];
                res -= q[j--];
            }
            if (sm > gt) continue;
            mxto(ans, res);
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	12880 KB	Output is correct
2	Correct	139 ms	12600 KB	Output is correct
3	Correct	159 ms	12800 KB	Output is correct
4	Correct	139 ms	12696 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	139 ms	12296 KB	Output is correct
7	Correct	71 ms	6548 KB	Output is correct
8	Correct	74 ms	6496 KB	Output is correct
9	Correct	145 ms	12876 KB	Output is correct
10	Correct	93 ms	12896 KB	Output is correct
11	Correct	90 ms	12804 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	41 ms	31956 KB	Output is correct
18	Correct	33 ms	32048 KB	Output is correct
19	Correct	33 ms	31956 KB	Output is correct
20	Correct	34 ms	29652 KB	Output is correct
21	Correct	34 ms	30804 KB	Output is correct
22	Correct	34 ms	31956 KB	Output is correct
23	Correct	32 ms	31956 KB	Output is correct

Subtask #4
0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	41 ms	31956 KB	Output is correct
18	Correct	33 ms	32048 KB	Output is correct
19	Correct	33 ms	31956 KB	Output is correct
20	Correct	34 ms	29652 KB	Output is correct
21	Correct	34 ms	30804 KB	Output is correct
22	Correct	34 ms	31956 KB	Output is correct
23	Correct	32 ms	31956 KB	Output is correct
24	Incorrect	114 ms	12840 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	41 ms	31956 KB	Output is correct
18	Correct	33 ms	32048 KB	Output is correct
19	Correct	33 ms	31956 KB	Output is correct
20	Correct	34 ms	29652 KB	Output is correct
21	Correct	34 ms	30804 KB	Output is correct
22	Correct	34 ms	31956 KB	Output is correct
23	Correct	32 ms	31956 KB	Output is correct
24	Incorrect	114 ms	12840 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	41 ms	31956 KB	Output is correct
18	Correct	33 ms	32048 KB	Output is correct
19	Correct	33 ms	31956 KB	Output is correct
20	Correct	34 ms	29652 KB	Output is correct
21	Correct	34 ms	30804 KB	Output is correct
22	Correct	34 ms	31956 KB	Output is correct
23	Correct	32 ms	31956 KB	Output is correct
24	Incorrect	114 ms	12840 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	12880 KB	Output is correct
2	Correct	139 ms	12600 KB	Output is correct
3	Correct	159 ms	12800 KB	Output is correct
4	Correct	139 ms	12696 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	139 ms	12296 KB	Output is correct
7	Correct	71 ms	6548 KB	Output is correct
8	Correct	74 ms	6496 KB	Output is correct
9	Correct	145 ms	12876 KB	Output is correct
10	Correct	93 ms	12896 KB	Output is correct
11	Correct	90 ms	12804 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	41 ms	31956 KB	Output is correct
29	Correct	33 ms	32048 KB	Output is correct
30	Correct	33 ms	31956 KB	Output is correct
31	Correct	34 ms	29652 KB	Output is correct
32	Correct	34 ms	30804 KB	Output is correct
33	Correct	34 ms	31956 KB	Output is correct
34	Correct	32 ms	31956 KB	Output is correct
35	Incorrect	114 ms	12840 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	166 ms	12880 KB	Output is correct
2	Correct	139 ms	12600 KB	Output is correct
3	Correct	159 ms	12800 KB	Output is correct
4	Correct	139 ms	12696 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	139 ms	12296 KB	Output is correct
7	Correct	71 ms	6548 KB	Output is correct
8	Correct	74 ms	6496 KB	Output is correct
9	Correct	145 ms	12876 KB	Output is correct
10	Correct	93 ms	12896 KB	Output is correct
11	Correct	90 ms	12804 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	41 ms	31956 KB	Output is correct
29	Correct	33 ms	32048 KB	Output is correct
30	Correct	33 ms	31956 KB	Output is correct
31	Correct	34 ms	29652 KB	Output is correct
32	Correct	34 ms	30804 KB	Output is correct
33	Correct	34 ms	31956 KB	Output is correct
34	Correct	32 ms	31956 KB	Output is correct
35	Incorrect	114 ms	12840 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

답안 #563878

Compilation message