oj.uz

Submission #579448

# Submission time Handle Problem Language Result Execution time Memory
579448 2022-06-19T07:42:30 Z Lucpp Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 24868 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 2e5+2;

ll A[2][MAX], T[2][MAX], P[2][MAX], dp[MAX];
int B[2][MAX];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < 2; i++){
        A[i][0] = P[i][0] = 0;
        for(int j = 1; j <= (i==0?n:m); j++){
            cin >> A[i][j] >> T[i][j] >> P[i][j];
            A[i][j] += A[i][j-1];
        }
    }
    
    for(int i = 0; i < 2; i++){
        B[i][0] = 0;
        int x = (i==0?m:n);
        for(int j = 1; j <= (i==0?n:m); j++){
            if(A[i][j] > T[i][j]) B[i][j] = -1;
            else if(A[i][j]+A[1-i][x] <= T[i][j]) B[i][j] = x;
            else B[i][j] = (int)(upper_bound(A[1-i], A[1-i]+x, T[i][j]-A[i][j])-A[1-i]-1);
        }
    }
    n++;
    B[0][n] = m;
    P[0][n] = 0;

    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = -INF;
        for(int j = 0; j < i; j++){
            if(B[0][j] <= B[0][i]){
                ll val = dp[j];
                for(int k = B[0][j]+1; k <= B[0][i]; k++){
                    if(B[1][k] >= j) val += P[1][k];
                }
                for(int k = j+1; k <= i; k++){
                    if(B[0][k] >= B[0][i]) val += P[0][k];
                }
                dp[i] = max(dp[i], val);
            }
        }
    }
    cout << dp[n] << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10086 ms 24868 KB Time limit exceeded
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 312 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 304 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 304 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 312 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 304 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 304 KB Output is correct
17 Correct 779 ms 568 KB Output is correct
18 Correct 3965 ms 568 KB Output is correct
19 Correct 3936 ms 564 KB Output is correct
20 Correct 4019 ms 556 KB Output is correct
21 Correct 2132 ms 592 KB Output is correct
22 Correct 4027 ms 500 KB Output is correct
23 Correct 3965 ms 628 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 312 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 304 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 304 KB Output is correct
17 Correct 779 ms 568 KB Output is correct
18 Correct 3965 ms 568 KB Output is correct
19 Correct 3936 ms 564 KB Output is correct
20 Correct 4019 ms 556 KB Output is correct
21 Correct 2132 ms 592 KB Output is correct
22 Correct 4027 ms 500 KB Output is correct
23 Correct 3965 ms 628 KB Output is correct
24 Execution timed out 10052 ms 21944 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 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 304 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 304 KB Output is correct
17 Correct 779 ms 568 KB Output is correct
18 Correct 3965 ms 568 KB Output is correct
19 Correct 3936 ms 564 KB Output is correct
20 Correct 4019 ms 556 KB Output is correct
21 Correct 2132 ms 592 KB Output is correct
22 Correct 4027 ms 500 KB Output is correct
23 Correct 3965 ms 628 KB Output is correct
24 Execution timed out 10052 ms 21944 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 312 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 304 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 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 304 KB Output is correct
17 Correct 779 ms 568 KB Output is correct
18 Correct 3965 ms 568 KB Output is correct
19 Correct 3936 ms 564 KB Output is correct
20 Correct 4019 ms 556 KB Output is correct
21 Correct 2132 ms 592 KB Output is correct
22 Correct 4027 ms 500 KB Output is correct
23 Correct 3965 ms 628 KB Output is correct
24 Execution timed out 10052 ms 21944 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10086 ms 24868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10086 ms 24868 KB Time limit exceeded
2 Halted 0 ms 0 KB -