oj.uz

Submission #579046

# Submission time Handle Problem Language Result Execution time Memory
579046 2022-06-18T10:43:47 Z Lucpp Two Dishes (JOI19_dishes) C++17
10 / 100
 482 ms 32852 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 2e5;

ll a[2][MAX], t[2][MAX], p[2][MAX];

vector<vector<ll>> dp;
vector<vector<bool>> vis;
ll calc(int i, int j, ll tim){
    if(vis[i][j]) return dp[i][j];
    vis[i][j] = true;
    dp[i][j] = -INF;
    if(i > 0) dp[i][j] = max(dp[i][j], calc(i-1, j, tim-a[0][i-1]) + p[0][i-1]*(tim<=t[0][i-1]));
    if(j > 0) dp[i][j] = max(dp[i][j], calc(i, j-1, tim-a[1][j-1]) + p[1][j-1]*(tim<=t[1][j-1]));
    return dp[i][j];
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < (i==0?n:m); j++)
            cin >> a[i][j] >> t[i][j] >> p[i][j];
    if(n <= 2000 && m <= 2000){
        dp.assign(n+1, vector<ll>(m+1));
        vis.assign(n+1, vector<bool>(m+1));
        vis[0][0] = true;
        ll tim = 0;
        for(int i = 0; i < n; ++i) tim += a[0][i];
        for(int i = 0; i < m; ++i) tim += a[1][i];
        cout << calc(n, m, tim) << "\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 10188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 99 ms 32824 KB Output is correct
18 Correct 94 ms 32852 KB Output is correct
19 Correct 84 ms 32724 KB Output is correct
20 Correct 80 ms 30464 KB Output is correct
21 Correct 84 ms 31616 KB Output is correct
22 Correct 84 ms 32764 KB Output is correct
23 Correct 93 ms 32784 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 99 ms 32824 KB Output is correct
18 Correct 94 ms 32852 KB Output is correct
19 Correct 84 ms 32724 KB Output is correct
20 Correct 80 ms 30464 KB Output is correct
21 Correct 84 ms 31616 KB Output is correct
22 Correct 84 ms 32764 KB Output is correct
23 Correct 93 ms 32784 KB Output is correct
24 Incorrect 417 ms 20176 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 99 ms 32824 KB Output is correct
18 Correct 94 ms 32852 KB Output is correct
19 Correct 84 ms 32724 KB Output is correct
20 Correct 80 ms 30464 KB Output is correct
21 Correct 84 ms 31616 KB Output is correct
22 Correct 84 ms 32764 KB Output is correct
23 Correct 93 ms 32784 KB Output is correct
24 Incorrect 417 ms 20176 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 99 ms 32824 KB Output is correct
18 Correct 94 ms 32852 KB Output is correct
19 Correct 84 ms 32724 KB Output is correct
20 Correct 80 ms 30464 KB Output is correct
21 Correct 84 ms 31616 KB Output is correct
22 Correct 84 ms 32764 KB Output is correct
23 Correct 93 ms 32784 KB Output is correct
24 Incorrect 417 ms 20176 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 10188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 10188 KB Output isn't correct
2 Halted 0 ms 0 KB -