TLEOJ Contest #16 - Dãy con thú vị - TLEOJ: TLE Online Judge

TLEOJ Contest #16 - Dãy con thú vị

Đ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

Output

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

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

Không có bình luận nào.