oj.uz

Submission #579102

# Submission time Handle Problem Language Result Execution time Memory
579102 2022-06-18T11:31:30 Z lcj Two Dishes (JOI19_dishes) C++17
10 / 100
 202 ms 91664 KB 
#include <bits/stdc++.h>

using namespace std;

typedef unsigned 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(m+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;
}

Compilation message

dishes.cpp: In function 'll explore(int, int)':
dishes.cpp:27:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if (ref != -1) return ref;
      |         ~~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 90408 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 12 ms 31588 KB Output is correct
2 Correct 14 ms 31668 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 13 ms 31568 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 14 ms 31552 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 14 ms 31572 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 13 ms 31572 KB Output is correct
15 Correct 14 ms 31572 KB Output is correct
16 Correct 13 ms 31648 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31588 KB Output is correct
2 Correct 14 ms 31668 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 13 ms 31568 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 14 ms 31552 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 14 ms 31572 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 13 ms 31572 KB Output is correct
15 Correct 14 ms 31572 KB Output is correct
16 Correct 13 ms 31648 KB Output is correct
17 Correct 111 ms 32212 KB Output is correct
18 Correct 104 ms 32268 KB Output is correct
19 Correct 102 ms 32296 KB Output is correct
20 Correct 94 ms 32272 KB Output is correct
21 Correct 99 ms 32284 KB Output is correct
22 Correct 100 ms 32212 KB Output is correct
23 Correct 105 ms 32248 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31588 KB Output is correct
2 Correct 14 ms 31668 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 13 ms 31568 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 14 ms 31552 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 14 ms 31572 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 13 ms 31572 KB Output is correct
15 Correct 14 ms 31572 KB Output is correct
16 Correct 13 ms 31648 KB Output is correct
17 Correct 111 ms 32212 KB Output is correct
18 Correct 104 ms 32268 KB Output is correct
19 Correct 102 ms 32296 KB Output is correct
20 Correct 94 ms 32272 KB Output is correct
21 Correct 99 ms 32284 KB Output is correct
22 Correct 100 ms 32212 KB Output is correct
23 Correct 105 ms 32248 KB Output is correct
24 Runtime error 182 ms 91664 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 12 ms 31588 KB Output is correct
2 Correct 14 ms 31668 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 13 ms 31568 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 14 ms 31552 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 14 ms 31572 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 13 ms 31572 KB Output is correct
15 Correct 14 ms 31572 KB Output is correct
16 Correct 13 ms 31648 KB Output is correct
17 Correct 111 ms 32212 KB Output is correct
18 Correct 104 ms 32268 KB Output is correct
19 Correct 102 ms 32296 KB Output is correct
20 Correct 94 ms 32272 KB Output is correct
21 Correct 99 ms 32284 KB Output is correct
22 Correct 100 ms 32212 KB Output is correct
23 Correct 105 ms 32248 KB Output is correct
24 Runtime error 182 ms 91664 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 12 ms 31588 KB Output is correct
2 Correct 14 ms 31668 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 13 ms 31572 KB Output is correct
5 Correct 13 ms 31568 KB Output is correct
6 Correct 14 ms 31564 KB Output is correct
7 Correct 13 ms 31572 KB Output is correct
8 Correct 13 ms 31572 KB Output is correct
9 Correct 14 ms 31552 KB Output is correct
10 Correct 13 ms 31572 KB Output is correct
11 Correct 14 ms 31572 KB Output is correct
12 Correct 14 ms 31572 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 13 ms 31572 KB Output is correct
15 Correct 14 ms 31572 KB Output is correct
16 Correct 13 ms 31648 KB Output is correct
17 Correct 111 ms 32212 KB Output is correct
18 Correct 104 ms 32268 KB Output is correct
19 Correct 102 ms 32296 KB Output is correct
20 Correct 94 ms 32272 KB Output is correct
21 Correct 99 ms 32284 KB Output is correct
22 Correct 100 ms 32212 KB Output is correct
23 Correct 105 ms 32248 KB Output is correct
24 Runtime error 182 ms 91664 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 202 ms 90408 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 202 ms 90408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -