Relax max
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
relaxmax.inp
Output:
relaxmax.out
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy gồm N ~(1 \le N \le 10^5)~ số nguyên ~A_1, A_2, A_N; (0 < A_i \le 10^5)~. Với bộ ba số (i,j,k) trong đó ~1 \le i < j < k \le N~ hãy tìm giá trị ~S= 3A_i - A_j - A_k~ sao cho S đạt giá trị lớn nhất.
Input:
Được cho bởi tệp relaxmax.inp có cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên N.
- Dòng thứ hai chứa N số nguyên ~A_1, A_2,..., A_N~ giữa các số cách nhau một khoảng trắng.
Output:
Được cho bởi tệp relaxmax.out có cấu trúc như sau:
- In ra một số duy nhất là số S lớn nhất tìm được.
Example
Input
9
95 5 74 65 89 62 3 2 37
Output
280
Bình luận
include<bits/stdc++.h> using namespace std; long long a[1000004],tr[1000003],sau[1000007],n,mx=-2e9; int main () { freopen("RELAXMAX.inp","r",stdin); freopen("RELAXMAX.out","w",stdout); iosbase::syncwith_stdio(false); cin.tie(NULL); cin>>n;for(int i=1;i<=n;++i) cin>>a[i]; tr[1]=a[1]; for(int i=1+2;i<=n;++i)tr[i]=max(tr[j-1],a[i]); sau[n]=a[n]; for(int i=n-1;i>=1;--i)sau[i]=min(sau[i+1],a[i]); for(int j=2;j<=n-1;++j) {long long z=3*tr[j-1]+a[j]-sau[j+1]; mx=max(mx,z);} cout<<mx; }