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

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
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

Comments

There are no comments at the moment.