| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P175SUMI - ROUND 5I - Sức mạnh tối đa |
Sau mỗi trận chiến Luffy đều ăn rất nhiều để bù đắp lại phần sức mạnh mà mình đã tiêu hao. Có tất cả N món ăn, mỗi món ăn có giá trị sức mạnh là a[i], Luffy chỉ cần ăn đúng M món ăn là được nhưng sẽ có K cách ăn để tăng được nhiều sức mạnh hơn. Giả sử nếu ăn món thứ y ngay sau món x thì sẽ được tăng thêm w đơn vị sức mạnh.
Hãy giúp Luffy đạt được sức mạnh tối đa sau khi ăn đúng M món.
Input
Dòng đầu gồm 3 số N,M,K
1<=N,M<=18,0<=K<=N*(N-1)
Dòng tiếp theo gồm N số a[i] (0<=a[i]<=10^9)
K dòng tiếp theo mỗi dòng gồm 2 số x,y,w (1<=x,y<=18, 0<=w<=10^9)
x,y,w có nghĩa là nếu ăn món y ngay sau món x sẽ được tăng thêm w sức mạnh.
Output
Kết quả lớn nhất tìm được.
Example
Test 1:
Input: 2 2 1
1 1
2 1 5
Output: 7
Test 2:
Input:
4 3 2
1 2 3 4
2 1 5
3 4 2
Output:
12
| Được gửi lên bởi: | adm |
| Ngày: | 2017-08-11 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
