oj.uz

Submission #579094

# Submission time Handle Problem Language Result Execution time Memory
579094 2022-06-18T11:25:15 Z lcj Two Dishes (JOI19_dishes) C++17
3 / 100
 198 ms 92144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int n, m;

struct Dish {
    ll a, s, p;
};
vector<Dish> d1, d2;
vector<ll> p1, p2;
ll dp[2001][2001];

ll getTime(int i1, int i2) {
    return p1[i1]+p2[i2];
}

ll explore(int i1, int i2) {
    if (i1 == n && i2 == m) {
        return 0;
    }
    ll &ref = dp[i1][i2];
    if (ref != -1) return ref;
    ll res = 0;
    bool iset = 0;
    if (i1 != n) {
        if (!iset) res = (getTime(i1, i2)+d1[i1].a <= d1[i1].s ? d1[i1].p : 0)+explore(i1+1, i2);
        res = max(res, (getTime(i1, i2)+d1[i1].a <= d1[i1].s ? d1[i1].p : 0)+ explore(i1+1, i2));
        iset = 1;
    }
    if (i2 != m) {
        if (!iset) res = (getTime(i1, i2)+d2[i2].a <= d2[i2].s ? d2[i2].p : 0)+ explore(i1, i2+1);
        res = max(res, (getTime(i1, i2)+d2[i2].a <= d2[i2].s ? d2[i2].p : 0)+ explore(i1, i2+1));
    }
    ref = res;
    return res;
}

void solve() {
    cin >> n >> m;
    ll a, s, p;
    p1.assign(n+1, 0);
    p2.assign(n+1, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> a >> s >> p;
        Dish dd = Dish {a, s, p};
        d1.push_back(dd);
        p1[i+1] = p1[i]+a;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> a >> s >> p;
        Dish dd = Dish {a, s, p};
        d2.push_back(dd);
        p2[i+1] = p2[i]+a;
    }
    memset(dp, -1, sizeof dp);
    cout << explore(0, 0) << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 198 ms 92144 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 13 ms 31644 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct
3 Correct 15 ms 31572 KB Output is correct
4 Correct 13 ms 31608 KB Output is correct
5 Correct 13 ms 31584 KB Output is correct
6 Correct 14 ms 31592 KB Output is correct
7 Correct 17 ms 31548 KB Output is correct
8 Correct 15 ms 31568 KB Output is correct
9 Correct 15 ms 31572 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 13 ms 31568 KB Output is correct
13 Correct 14 ms 31592 KB Output is correct
14 Correct 13 ms 31560 KB Output is correct
15 Correct 14 ms 31568 KB Output is correct
16 Correct 13 ms 31568 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31644 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct
3 Correct 15 ms 31572 KB Output is correct
4 Correct 13 ms 31608 KB Output is correct
5 Correct 13 ms 31584 KB Output is correct
6 Correct 14 ms 31592 KB Output is correct
7 Correct 17 ms 31548 KB Output is correct
8 Correct 15 ms 31568 KB Output is correct
9 Correct 15 ms 31572 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 13 ms 31568 KB Output is correct
13 Correct 14 ms 31592 KB Output is correct
14 Correct 13 ms 31560 KB Output is correct
15 Correct 14 ms 31568 KB Output is correct
16 Correct 13 ms 31568 KB Output is correct
17 Correct 111 ms 32292 KB Output is correct
18 Correct 100 ms 32336 KB Output is correct
19 Correct 118 ms 32296 KB Output is correct
20 Correct 99 ms 32212 KB Output is correct
21 Runtime error 128 ms 65180 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31644 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct
3 Correct 15 ms 31572 KB Output is correct
4 Correct 13 ms 31608 KB Output is correct
5 Correct 13 ms 31584 KB Output is correct
6 Correct 14 ms 31592 KB Output is correct
7 Correct 17 ms 31548 KB Output is correct
8 Correct 15 ms 31568 KB Output is correct
9 Correct 15 ms 31572 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 13 ms 31568 KB Output is correct
13 Correct 14 ms 31592 KB Output is correct
14 Correct 13 ms 31560 KB Output is correct
15 Correct 14 ms 31568 KB Output is correct
16 Correct 13 ms 31568 KB Output is correct
17 Correct 111 ms 32292 KB Output is correct
18 Correct 100 ms 32336 KB Output is correct
19 Correct 118 ms 32296 KB Output is correct
20 Correct 99 ms 32212 KB Output is correct
21 Runtime error 128 ms 65180 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31644 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct
3 Correct 15 ms 31572 KB Output is correct
4 Correct 13 ms 31608 KB Output is correct
5 Correct 13 ms 31584 KB Output is correct
6 Correct 14 ms 31592 KB Output is correct
7 Correct 17 ms 31548 KB Output is correct
8 Correct 15 ms 31568 KB Output is correct
9 Correct 15 ms 31572 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 13 ms 31568 KB Output is correct
13 Correct 14 ms 31592 KB Output is correct
14 Correct 13 ms 31560 KB Output is correct
15 Correct 14 ms 31568 KB Output is correct
16 Correct 13 ms 31568 KB Output is correct
17 Correct 111 ms 32292 KB Output is correct
18 Correct 100 ms 32336 KB Output is correct
19 Correct 118 ms 32296 KB Output is correct
20 Correct 99 ms 32212 KB Output is correct
21 Runtime error 128 ms 65180 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31644 KB Output is correct
2 Correct 15 ms 31572 KB Output is correct
3 Correct 15 ms 31572 KB Output is correct
4 Correct 13 ms 31608 KB Output is correct
5 Correct 13 ms 31584 KB Output is correct
6 Correct 14 ms 31592 KB Output is correct
7 Correct 17 ms 31548 KB Output is correct
8 Correct 15 ms 31568 KB Output is correct
9 Correct 15 ms 31572 KB Output is correct
10 Correct 15 ms 31568 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 13 ms 31568 KB Output is correct
13 Correct 14 ms 31592 KB Output is correct
14 Correct 13 ms 31560 KB Output is correct
15 Correct 14 ms 31568 KB Output is correct
16 Correct 13 ms 31568 KB Output is correct
17 Correct 111 ms 32292 KB Output is correct
18 Correct 100 ms 32336 KB Output is correct
19 Correct 118 ms 32296 KB Output is correct
20 Correct 99 ms 32212 KB Output is correct
21 Runtime error 128 ms 65180 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

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