VNOJ Round 01 - THREE

Xem dạng PDF

Gửi bài giải


Điểm: 0,01 (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

Hãy đọc nội quy trước khi bình luận.



  • -4
    nguyenthanhnhan13032009  đã bình luận lúc 17, Tháng 9, 2024, 8:04

    include<bits/stdc++.h>

    using namespace std; const int maxn=5e3; int ans=0,n,a[maxn+5],t,m,f[maxn+5]; int main(){ cin.tie(0)->syncwithstdio(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=n;i;i--)f[i]=max(f[i+1],a[i]); for(int i=1;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(a[j]>a[i]){ if(f[j+1]>a[j])ans=max(ans,a[i]+a[j]+f[j+1]); } } } cout<<ans; return 0; }


  • -3
    laiquanghuy  đã bình luận lúc 1, Tháng 5, 2024, 13:10

    nể cái b code bài này bằng py luôn


  • -1
    holybridge001  đã bình luận lúc 30, Tháng 3, 2024, 4:44

    //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; }


  • -1
    moiaaaaaaaaa  đã bình luận lúc 17, Tháng 2, 2024, 15:13

    ai có sol ko


  • 5
    gv_thcsttme_dangngoclanchi  đã bình luận lúc 13, Tháng 2, 2024, 9:18

    bài này giống bài LIS


    • -1
      trankhvan  đã bình luận lúc 30, Tháng 6, 2024, 22:18

      hậu tố thôi bạn


  • -7
    huy_lovely  đã bình luận lúc 13, Tháng 2, 2024, 0:39 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -7
    GiangPiano  đã bình luận lúc 6, Tháng 2, 2024, 2:54 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -30
    flexchilavotinh  đã bình luận lúc 3, Tháng 2, 2024, 11:05

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.