Nộp bài
Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Dạng bài
Ngôn ngữ cho phép
Assembly, bf, C++, Haskell, Java, NASM, Pascal, pypy, pypy3, Python
Cho số nguyên dương L và dãy số nguyên a_1, a_2,..., a_{n-1}, a_n (a_i \leq L). Một dãy con khác rỗng của a được tạo ra bằng cách xóa đi một vài phần tử (có thể không xóa phần tử nào, nhưng phải giữ lại ít nhất một phần tử) và giữ nguyên thứ tự các phần tử còn lại. Độ thú vị của một dãy b_1, b_2,..., b_{m-1}, b_m được định nghĩa là:
\sum_{i = 1}^{i \le m} p[b[i]] + \sum_{i = 1}^{i \le m} q[b[i]][b[i+1]]
Tìm độ đẹp lớn nhất có thể của một dãy con không rỗng của a
Input and Output
Input
- Dòng đầu gồm hai số nguyên n, L (n \leq 10^5, 1 \leq L \leq min(n, 50))
- Dòng thứ hai chứa n số nguyên dương a_1, a_2,..., a_{n-1}, a_n
- Dòng thứ ba gồm L số nguyên p_1, p_2,...,p_L (|p_i| \leq 10^4)
- L dòng tiếp theo, dòng thứ i chứa L số nguyên q_{i1}, q_{i2},..., q_{iL} (|q_{ij}| \leq 10^4)
Output
- Một dòng duy nhất chứa số nguyên là độ đẹp lớn nhất tìm được.
Scoring
- Subtask 1 (40\%): n \leq 20
- Subtask 2 (30\%): n \leq 3*10^3
- Subtask 3 (30\%): Không có ràng buộc gì thêm
Test 1
Input
4 3
1 2 3 2
1 2 3
1 2 3
1 2 3
1 2 3
Output
15
Note
Dãy con cần tìm là {1, 2, 3, 4}. Độ đẹp là (1+2+3+2) + (2+3+2) = 8+7 = 15
Test 2
Input
7 4
3 2 3 4 1 4 3
1 -1 3 -1
1 0 10 4
-100 -10 1 7
-3 -2 4 -2
3 2 1 0
Output
24
Note
Dãy con cần tìm là {3, 3, 4, 1, 3}. Độ đẹp là (3+3-1+1+3)+(4-2+3+10) = 9+15 = 24
Bình luận