trang chủ / đề bài / icpc22_mt_g

Ruy băng

Đề bài

Mô tả

Jeremy có một dải ruy băng dài gồm N mảnh bằng nhau, trên mỗi mảnh ghi một số nguyên; có thể mô tả dải ruy băng bằng mảng A gồm N số nguyên. Jeremy muốn cắt từ dải ruy băng ra một số đoạn (ít nhất một đoạn), mỗi đoạn gồm đúng K mảnh liên tiếp; các đoạn không được chồng lên nhau và có thể bỏ đi một số mảnh không dùng. Độ đẹp B của một đoạn là tổng các số trên các mảnh của nó.

Ví dụ với A=[−3,1,−2,6,2,3] và K=2, Jeremy có thể cắt ra [[−3,1],[6,2]], hoặc [[−2,6],[2,3]], hoặc [[−3,1],[−2,6],[2,3]], ... nhưng không thể cắt ra [[−3,1,−2],[2,3]] (đoạn đầu có 3 mảnh) hay [[−3,−2],[6,2]] (các mảnh −3 và −2 không liền nhau).

Sau đó Jeremy dán các đoạn đã cắt lại với nhau, giữ nguyên thứ tự như trên dải ban đầu, và tô màu các đoạn đen hoặc trắng xen kẽ nhau (đen, trắng, đen, trắng, ... hoặc trắng, đen, trắng, đen, ...).

Giả sử Jeremy cắt ra Q đoạn, đoạn thứ j có độ đẹp Bj và hệ số màu Mj, với Mj=1 nếu đoạn được tô trắng và Mj=−1 nếu được tô đen. Giá trị của dải ruy băng mới là

L=∑j=1QMj×Bj.

Hãy tìm giá trị L lớn nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T (1≤T≤10) là số bộ dữ liệu.

Mỗi bộ dữ liệu gồm hai dòng:

  • Dòng thứ nhất chứa hai số nguyên N và K (1≤K≤N≤2×105) là số mảnh của dải ruy băng và độ dài mỗi đoạn.
  • Dòng thứ hai chứa N số nguyên A1,A2,…,AN (−109≤Ai≤109).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra giá trị L lớn nhất trên một dòng.

Ràng buộc

  • 1≤T≤10.
  • 1≤K≤N≤2×105.
  • −109≤Ai≤109.

Ví dụ

Input Output Giải thích
3
3 3
-2 -3 2
5 2
6 5 2 -5 -6
6 2
-3 1 -2 6 2 3
3
22
10
Bộ thứ nhất: lấy cả dải làm một đoạn có độ đẹp −3 và tô đen. Bộ thứ ba: lấy hai đoạn [−3,1] (tô đen) và [6,2] (tô trắng), bỏ các mảnh −2, 2, 3; L=−1×(−3+1)+1×(6+2)=10.
1
4 1
5 -1 3 -2
11 Lấy cả bốn mảnh, tô trắng, đen, trắng, đen: 5+1+3+2=11.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0