Chọn nhóm

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
_minhduc
Dạng bài
Điểm: 2100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(n\) người, người thứ \(i\) (\(1 \le i \le n\)) được gán cho một số nguyên \(a_i\) (\(|a_i| \le 10^5\)), người ta muốn chọn ra \(3 \times k\) người chia thành \(k\) nhóm, mỗi nhóm gồm ba người. Sự hợp tác của một nhóm gồm ba người được tính bằng tích các số gán cho ba người đó, cụ thể nếu ba người \(i_1,i_2,i_3\) (\(1 \le i_1,i_2,i_3 \le n\)) được xếp vào một nhóm thì sự hợp tác được tính bằng \(a_{i_1} \times a_{i_2} \times a_{i_3}\).

Yêu cầu: Hãy tìm cách chọn \(k\) nhóm để sự hợp tác của \(k\) nhóm là lớn nhất.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\).

Output

  • Một số nguyên là tổng sự hợp tác của \(k\) nhóm.

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(k = 1, n \le 10\).
  • Subtask \(2\) (\(20\%\) số điểm): \(k = 1, n \le 10^5\).
  • Subtask \(3\) (\(20\%\) số điểm): \(k = 2, n \le 10\).
  • Subtask \(4\) (\(10\%\) số điểm): \(k = 2, n \le 10^5\).
  • Subtask \(5\) (\(20\%\) số điểm): \(k = 3, n \le 10^5\).
  • Subtask \(6\) (\(20\%\) số điểm): \(k \le 5, n \le 10^5\).

Example

Test 1
Input 
9 2
1 2 3 4 -2 6 7 8 -9
Output 
408
Note

\(8 \times 7 \times 6 + 4 \times (-9) \times (-2) = 408\).

Bình luận


  • 2
    congdz    4:34 p.m. 22 Tháng 7, 2024

    include <bits/stdc++.h>

        using namespace std;
    int n,k,d,c;
    long long kq1,kq2,t,a[100005];
    int main()
    {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    // freopen("test.INP","r",stdin);
    // freopen("test.OUT","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    d=1;c=n;
    while(k>0)
    {
    kq1=a[d]a[d+1]a[c];
    kq2=a[c]a[c-1]a[c-2];
    // cout<<kq1<<" "<<kq2<<'\n';
    long long siu=max(kq1,kq2);
    t=t+siu;
    if(siu==kq1)
    {
    d=d+2;c=c-1;
    }
    else
    {
    c=c-3;
    }
    k--;
    }
    cout<<t;
    return 0;
    }

      • 1 bình luận nữa