VNOJ Round 01 - THREE

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
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~.

Comments

Please read the guidelines before commenting.


  • -3
    nguyenthanhnhan13032009  commented on Sept. 17, 2024, 8:04 a.m.

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


  • -2
    laiquanghuy  commented on May 1, 2024, 1:10 p.m.

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


  • 0
    holybridge001  commented on March 30, 2024, 4:44 a.m.

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


  • 0
    moiaaaaaaaaa  commented on Feb. 17, 2024, 3:13 p.m.

    ai có sol ko


  • 5
    gv_thcsttme_dangngoclanchi  commented on Feb. 13, 2024, 9:18 a.m.

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


    • 0
      trankhvan  commented on June 30, 2024, 10:18 p.m.

      hậu tố thôi bạn


  • -6
    huy_lovely  commented on Feb. 13, 2024, 12:39 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    GiangPiano  commented on Feb. 6, 2024, 2:54 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -29
    flexchilavotinh  commented on Feb. 3, 2024, 11:05 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.