結果
問題 |
No.1117 数列分割
|
ユーザー |
|
提出日時 | 2025-03-24 22:17:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,353 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 88,720 KB |
実行使用メモリ | 14,772 KB |
最終ジャッジ日時 | 2025-03-24 22:17:26 |
合計ジャッジ時間 | 6,077 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 25 |
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; int N, K, M; vector<int> A; int max_score = 0; // Hàm tính tổng giá trị tuyệt đối của từng nhóm int calculateScore(const vector<vector<int>>& groups) { int score = 0; for (const auto& group : groups) { int sum = 0; for (int x : group) sum += x; score += abs(sum); } return score; } // Hàm thử tất cả cách chia nhóm (Backtracking) void backtrack(int idx, vector<vector<int>>& groups) { if (idx == N) { if (groups.size() == K) { max_score = max(max_score, calculateScore(groups)); } return; } // Thêm phần tử A[idx] vào nhóm hiện tại nếu chưa đầy M phần tử if (!groups.empty() && groups.back().size() < M) { groups.back().push_back(A[idx]); backtrack(idx + 1, groups); groups.back().pop_back(); } // Bắt đầu một nhóm mới (nếu chưa đủ K nhóm) if (groups.size() < K) { groups.push_back({A[idx]}); backtrack(idx + 1, groups); groups.pop_back(); } } int main() { cin >> N >> K >> M; A.resize(N); for (int i = 0; i < N; i++) cin >> A[i]; vector<vector<int>> groups; backtrack(0, groups); cout << max_score << endl; return 0; }