fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5.  
  6. using namespace std;
  7.  
  8. // Hàm giải quyết từng bộ test
  9. void solve() {
  10.     int n;
  11.     if (!(cin >> n)) return;
  12.  
  13.     // Đọc mảng a (0-based indexing)
  14.     vector<long long> a(n);
  15.     long long total_sum = 0;
  16.     for (int i = 0; i < n; ++i) {
  17.         cin >> a[i];
  18.         total_sum += a[i];
  19.     }
  20.  
  21.     // 1. Tính mảng tổng tiền tố (Prefix Sum) P
  22.     // P[i] là tổng của i phần tử đầu tiên (a[0] đến a[i-1])
  23.     // P[0] = 0
  24.     vector<long long> P(n + 1, 0);
  25.     for (int i = 0; i < n; ++i) {
  26.         P[i + 1] = P[i] + a[i];
  27.     }
  28.  
  29.     long long max_profit = 0;
  30.  
  31.     // 2. max_L_value sẽ lưu max_{1 <= l <= r} (P[l-1] - l^2 + l)
  32.     // l ở đây là chỉ số 1-based (từ 1 đến n)
  33.  
  34.     // Khởi tạo max_L_value cho l=1: P[0] - 1^2 + 1 = 0 - 1 + 1 = 0
  35.     // Ta sử dụng giá trị MIN_LONG_LONG để đảm bảo giá trị đầu tiên được gán đúng
  36.     long long max_L_value = -2e18; // Khởi tạo với giá trị rất nhỏ
  37.  
  38.     // 3. Duyệt r từ 1 đến n (r là chỉ số 1-based)
  39.     for (int r = 1; r <= n; ++r) {
  40.  
  41.         // A. Cập nhật max_L_value (xét thêm l=r)
  42.         // L_r = P[r-1] - r^2 + r
  43.  
  44.         long long r_long = (long long)r;
  45.         long long current_L_r = P[r - 1] - r_long * r_long + r_long; // Đã sửa lỗi dấu: + r_long
  46.         max_L_value = max(max_L_value, current_L_r);
  47.  
  48.         // B. Tính lợi nhuận tối đa cho r cố định
  49.         // Profit_r = (r^2 + r - P[r]) + max_L_value
  50.  
  51.         long long term_R = r_long * r_long + r_long - P[r];
  52.         long long current_max_profit = term_R + max_L_value;
  53.  
  54.         // C. Cập nhật lợi nhuận tối đa chung
  55.         max_profit = max(max_profit, current_max_profit);
  56.     }
  57.  
  58.     // 4. Kết quả là tổng ban đầu + lợi nhuận tối đa (có thể là 0 nếu không thay thế)
  59.     cout << total_sum + max_profit << endl;
  60. }
  61.  
  62. int main() {
  63.     // Tăng tốc độ I/O
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL);
  66.  
  67.     int t;
  68.     if (!(cin >> t)) return 0;
  69.     while (t--) {
  70.         solve();
  71.     }
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
3
2 5 1
2
4 4
4
1 3 2 1
5
3 2 0 9 10
stdout
copy 
13
8
20
32
https://ideone.com/Y4z28t
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!