VNOJ Round 01 - THREE
Xem dạng PDF
Gửi bài giải
Điểm:
0,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Nauw có một dãy ~a~ gồm ~n~ phần tử phân biệt: ~a_1, a_2, a_3, \ldots, a_n~.
Tìm tổng ~a_i+a_j+a_k~ lớn nhất sao cho:
~1 \le i < j < k \le n~.
~a_i < a_j < a_k~.
Nếu như không tồn tại ~i, j, k~ thỏa mãn thì in ra ~-1~. Hãy giúp Nauw giải quyết bài toán này nhé!
Input
Dòng đầu tiên ghi một số nguyên ~n~ là số phần tử của dãy ~a~ (~3 \le n \le 5000~).
Dòng thứ hai ghi ~n~ số nguyên dương phân biệt mô tả dãy ~a~ (~1\le a_i \le 10^5~).
Output
- In ra một số nguyên dương duy nhất là kết quả của bài hoặc in ra ~-1~ nếu như không có đáp án.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~3\le n \le 300~ |
| 2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
7
1 5 2 3 4 9 6
Sample Output 1
16
Notes
Giá trị tốt nhất đạt được khi ~i=4, j=5, k=6~, và tổng là ~a_i + a_j + a_k = 3 + 4 + 9 = 16~.
Bình luận
//SPOILER : Mình mới tập làm thuật toán và cấu trúc dữ liệu nếu bạn nào có cách nhanh hơn thì giúp mình với, mình cảm ơn.
include <iostream>
include <vector>
using namespace std;
int main() { iosbase::syncwithstdio(false); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } int maxSum = -1; for (int j = 1; j < n - 1; ++j) { int maxleft = -1, maxright = -1; for (int i = 0; i < j; ++i) { if (a[i] < a[j]) { maxleft = max(maxleft, a[i]); } } for (int k = j + 1; k < n; ++k) { if (a[j] < a[k]) { maxright = max(maxright, a[k]); } } if (maxleft != -1 && maxright != -1) { int sum = maxleft + a[j] + max_right; maxSum = max(maxSum, sum); } } cout << maxSum << '\n'; return 0; }
ai có sol ko
bài này giống bài LIS
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.