XẾP KHỐI

Bob có một bộ đồ chơi gồm \(n\) khối gỗ, khối gỗ thứ \(i\) có độ cao \(h_{i}\).

Hôm nay, cậu quyết định lấy \(k\) khối gỗ trong bộ đồ chơi của mình để xây tháp. Một dãy \(k\) khối gỗ có độ cao \(v_{1},\ v_{2},\ ...,\ v_{k}\) sẽ xây được một tòa tháp có độ chênh vênh là \(\min_{1 \leq i < j \leq k}{|v_{i} - v_{j}|}\)

Lựa mãi không biết nên lấy những khối gỗ nào cho phù hợp. Vì vậy, thay vì chơi xếp hình, Bob chuyển hướng sang tính độ chênh vênh của mọi tòa tháp có thể xây dựng được.

Bạn hãy giúp Bob tính xem, trong tất cả các cách chọn \(k\) khối gỗ để xây tháp, tổng độ chênh vênh sẽ là bao nhiêu. Vì kết quả có thể rất lớn, in ra phần dư tổng tính được sau khi chia cho 998244353

Dữ liệu vào:

+ Dòng đầu tiên chứa hai số nguyên dương \(n,\ k\) là số khối gỗ trong bộ đồ chơi của Bob và số khối gỗ để xây tháp \((2 \leq k \leq n \leq 10^{3})\).

+ Dòng thứ hai chứa \(n\) số nguyên dương \(h_{1},\ h_{2},\ ...,\ h_{n}\), số thứ \(i\) là độ cao của khối gỗ thứ \(i\ (0 \leq h_{i} \leq 10^{5})\).

Kết quả:

+ Một dòng duy nhất chứa kết quả của bài toán

Ví dụ:

Input Output Input Output Input Output
5 3
5 4 2 1 3
11 6 4
2 6 8 10 1 5
19 4 3
1 2 2 3
2

Ràng buộc:

+ Subtask 1 (30% điểm): \(n,\ k,\ h_{i}\ \leq \ 100\).

+ Subtask 2 (40% điểm): \(n,\ k,\ h_{i}\ \leq \ 600\).

+ Subtask 3 (30% điểm): Không có ràng buộc gì thêm.

Bạn cần đăng nhập để nộp bài

hpcode.edu.vn
Code tích cực
Trong 24h
  1. npk1605 (5/10)
  2. tuythoi213 (4/6)
  3. tung (2/5)
Trong 7 ngày
  1. nguyenanhvu (40/64)
  2. khieuquan (35/59)
  3. ngokhang (27/55)
Trong 30 ngày
  1. quechi (85/105)
  2. dangphong3108 (79/125)
  3. kiennhientv (79/179)
Thống kê
AC/Sub: 97887/180710
Pascal: 17121
C++: 130348
Python: 33199
Lượt xem/tải tests: 38905

Lưu Hải Phong - 2020
[email protected]