DAYSO6 - Dãy số (OLP Không chuyên 2009)

DAYSO6 - Dãy số (OLP Không chuyên 2009)

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: admin

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Tìm giá trị lớn nhất của hàm f(i, j, k) = a_i + 2×a_j + 3×a_k với 1≤ i < j < k ≤ n.
Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì f(1, 2, 5)= -1 + 2×2 + 3×5 = 18 là lớn nhất.
Dữ liệu nhập:
- Dòng thứ nhất là số nguyên n (3 ≤ n ≤ 10⁵).
- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n  mỗi số cách nhau một khoảng trắng (|a_i| ≤ 10⁹)
Dữ liệu xuất:
- Là giá trị lớn nhất của hàm f(i, j, k) tìm được.

Ví dụ

• input
  5
  -1 2 -2 -3 5
  output
  18
  /*******************/
  #include<bits/stdc++.h>
  #define For(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
  using namespace std;
  const int maxn = 10 + 1e5;
  const int INF = 0x3f3f3f3f;
  typedef long long LL;
  typedef pair<int,int> II;
  
  #define fi first
  #define se second
  long long a[maxn], ma1[maxn], ma2[maxn], ma3[maxn];
  int main()
  {
  #ifndef ONLINE_JUDGE
  #define TASK "ABC"
      freopen(TASK".inp","r",stdin);
      freopen(TASK".out","w",stdout);
  #endif
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
      int n;
      cin >> n;
      ma1[0] = LONG_LONG_MIN;
      for(int i = 1 ;i <= n; ++i)
      {
          cin >> a[i];
          ma1[i] = max(ma1[i-1], a[i]);
      }
      ma2[1] = LONG_LONG_MIN;
      for(int i = 2; i <= n; ++i)
      {
          ma2[i] = ma2[i-1];
          ma2[i] = max(ma2[i], ma1[i-1] + 2 * a[i]);
      }
      ma3[2] = LONG_LONG_MIN;
      for(int i = 3; i <= n; ++i)
      {
          ma3[i] = ma3[i-1];
          ma3[i] = max(ma3[i], ma2[i-1] + 3 * a[i]);
      }
      cout << ma3[n];
      return 0;
  }