| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P131SUMG - SUM1 G - Giá trị của dãy số |
Định nghĩa giá trị của dãy số là sự chênh lệch giữa số lớn nhất và nhỏ nhất trong dãy. Ví dụ, giá trị của dãy (3, 1, 7, 2) là 6, và giá trị của (42, 42) là 0.
Tìm tổng của các giá trị của tất cả các dãy con chứa các phần tử liên tiếp trong dãy số đã cho.
Input
Dòng đầu tiên của input chứa một số nguyên N ( 2<= N <= 300 000), số phần tử của dãy.
N dòng tiếp theo chứa các phần tử của dãy số. Mỗi phần tử là một số nguyên dương không lớn hơn 100 000 000.
Output
In ra một số nguyên là đáp số của bài toán.
Example
Test 1.
Input:
3
1
2
3
Ouput:
4
Test 2.
Input:
4
7
5
7
5
Ouput:
12
Test 3.
Input:
4
3
1
7
2
Ouput:
31
Giải thích test 3:
-Các tập con có 1 phần tử có độ chênh lệch bằng 0
-Các tập con có 2 phần tử: (3,1) là 2, (1,7) là 6, (7,2) là 5
-Các tập con có 3 phần tử: (3,1,7) là 6 , (1,7,2) là 6
-Các tập con có 4 phần tử là (3,1,7,2) là 6
Tổng là: 6+6+6+6+5+2=31.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-03 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2024-07-04 13:45:42
#include <iostream> #include <cmath> int a[100000]; int dp[2][100000][21]; unsigned long long solve(int k, int f, int t) { if (f > t) return 0; int h = log2(t - f + 1); int p; if (k) { p = (a[dp[k][f][h]] > a[dp[k][t - (1 << h) + 1][h]]) ? dp[k][f][h] : dp[k][t - (1 << h) + 1][h]; } else { p = (a[dp[k][f][h]] < a[dp[k][t - (1 << h) + 1][h]]) ? dp[k][f][h] : dp[k][t - (1 << h) + 1][h]; } unsigned long long res = 1ull * (p - f + 1) * (t - p + 1) * a[p]; res += solve(k, f, p - 1) + solve(k, p + 1, t); return res; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); int n; std::cin >> n; for (int i = 1; i <= n; ++i) { std::cin >> a[i]; dp[0][i][0] = i; dp[1][i][0] = i; } for (int j = 1; (1 << j) <= n; ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) for (int k = 0; k < 2; ++k) dp[k][i][j] = (a[dp[k][i][j - 1]] > a[dp[k][i + (1 << (j - 1))][j - 1]]) == k ? dp[k][i][j - 1] : dp[k][i + (1 << (j - 1))][j - 1]; std::cout << solve(1, 1, n) - solve(0, 1, n); } |
|
|
2022-03-16 18:02:40
bạn nào làm được bài này gửi cho mọi người đi |
|
|
2019-08-15 19:02:45
40 :( |
|
|
2019-07-11 10:54:41
Sinh =)) |
|
|
2018-07-26 16:57:50
def solved(arr,n): new_arr = list.copy(arr) lst = [] while new_arr != []: i = 0 x = new_arr[i:n] if len(x) == n: lst.append(new_arr[i:n]) new_arr.remove(new_arr[i]) result = 0 for i in lst: a = max(i) - min(i) result += a return result if __name__ == '__main__': x = int(input()) arr = [] for _ in range(x): arr.append(int(input())) kq = 0 for i in range(1,x+1): kq += solved(arr,i) print(kq) mãi vẫn 20 :) |
|
|
2017-12-10 17:37:11
bài này hay vãi :v mỗi tội mình không làm được |
|
|
2017-05-24 05:11:42
làm mãi chỉ có 20 điểm :( |
|
|
2015-08-18 17:53:48 62
giống bài đo chiều cao vãi :v |
