QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #531100 | #391. Commando | isirazeev | 90 | 322ms | 42028kb | C++20 | 1.6kb | 2024-08-24 18:21:42 | 2024-08-24 18:21:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct line {
int k, b;
line(int _k, int _b) : k(_k), b(_b) {};
[[nodiscard]] int getX(int x) const {
return k * x + b;
}
};
long double intersectX(line a, line b) {
return (long double) (b.b - a.b) / (long double) (a.k - b.k);
}
deque<line> st;
int sz = 0;
void add_line(line add) {
while (sz >= 2 && intersectX(st[sz - 2], st[sz - 1]) >= intersectX(st[sz - 2], add))
st.pop_back(), sz--;
st.emplace_back(add), sz++;
}
int get_X(int x) {
if (sz == 1) return st[0].getX(x);
int l = 0, r = sz - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (intersectX(st[mid], st[mid + 1]) <= (long double) x) l = mid;
else r = mid;
}
return st[r].getX(x);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, a, b, c;
cin >> n >> a >> b >> c;
int x[n], pref[n], dp[n];
for (int i = 0; i < n; i++) {
cin >> x[i];
pref[i] = x[i] + (i > 0 ? pref[i - 1] : 0);
}
dp[0] = a * x[0] * x[0] + b * x[0] + c;
add_line(line(-2 * a * pref[0], dp[0] + a * pref[0] * pref[0] - b * pref[0]));
for (int i = 1; i < n; i++) {
dp[i] = a * pref[i] * pref[i] + b * pref[i] + c;
dp[i] = max(dp[i], get_X(pref[i]) + a * pref[i] * pref[i] + b * pref[i] + c);
add_line(line(-2 * a * pref[i], dp[i] + a * pref[i] * pref[i] - b * pref[i]));
}
cout << dp[n - 1];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3624kb
input:
500 -1 100 -1000 12 58 12 11 22 59 41 54 5 16 87 74 88 55 21 50 16 79 94 10 96 90 22 12 60 6 78 96 59 8 52 3 51 63 59 96 90 56 57 25 38 62 89 47 12 77 3 14 62 75 65 76 66 18 29 4 54 62 41 47 22 50 73 30 43 58 91 69 33 68 59 23 82 79 94 34 12 63 17 81 49 7 10 13 51 91 86 44 31 82 59 92 73 30 31 23 48...
output:
362631
result:
ok single line: '362631'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
input:
1000 -1 120 -1200 59 29 3 17 27 65 62 34 100 99 92 8 90 10 23 72 65 99 59 25 56 59 70 40 20 63 97 41 39 82 97 85 58 5 48 60 16 6 22 44 24 13 47 34 18 75 34 73 37 79 66 41 99 39 68 38 45 10 12 53 57 72 20 70 34 19 87 39 22 15 41 79 46 56 88 62 41 58 46 100 9 30 84 45 55 67 30 4 17 67 16 47 7 63 36 93...
output:
1588509
result:
wrong answer 1st lines differ - expected: '1588599', found: '1588509'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3804kb
input:
5000 -1 130 -2000 4 89 66 15 64 66 19 17 43 88 21 7 73 99 97 33 57 11 4 50 86 29 68 34 45 53 82 16 54 90 65 26 30 97 57 84 61 74 84 78 73 83 13 48 95 41 6 9 48 52 100 67 30 67 76 4 96 42 76 26 64 39 47 27 48 13 93 52 27 2 14 62 72 75 12 98 99 11 23 85 59 38 97 87 56 29 66 93 89 92 50 80 9 14 36 73 8...
output:
7042743
result:
ok single line: '7042743'
Test #4:
score: 10
Accepted
time: 0ms
memory: 3864kb
input:
8000 -1 160 -2000 14 82 61 85 41 10 34 17 47 91 87 79 28 1 3 17 96 24 34 58 85 72 95 56 57 6 64 2 2 33 36 90 13 79 5 83 16 23 63 69 36 63 91 65 66 33 99 67 5 68 12 85 84 40 9 50 40 33 20 78 50 40 58 95 2 83 36 89 70 11 23 18 88 43 39 18 89 10 84 13 97 57 13 52 31 90 22 13 36 68 83 17 34 89 2 44 25 2...
output:
23226559
result:
ok single line: '23226559'
Test #5:
score: 10
Accepted
time: 3ms
memory: 4148kb
input:
10000 -2 200 0 82 20 17 6 91 4 25 5 38 6 5 92 38 83 65 86 24 75 48 52 12 52 90 29 38 40 59 42 47 86 16 84 73 54 22 10 16 60 85 85 82 15 50 36 46 91 76 41 41 95 87 41 53 7 22 43 61 76 31 12 56 89 77 9 13 31 53 50 24 28 84 86 3 12 79 83 55 83 40 15 19 73 37 95 17 40 58 98 29 8 28 9 19 33 19 18 20 25 7...
output:
33519580
result:
ok single line: '33519580'
Test #6:
score: 10
Accepted
time: 29ms
memory: 7088kb
input:
100000 -1 2000 -500000 5 99 54 71 99 95 65 24 22 88 59 83 63 87 55 79 35 22 99 6 73 70 35 92 60 46 45 87 44 62 18 45 53 53 16 54 36 31 21 71 97 14 38 43 64 67 35 2 52 28 66 72 80 71 66 3 4 17 62 51 92 55 94 40 39 33 13 93 23 94 64 72 12 48 70 81 30 80 17 48 50 75 79 98 22 94 28 91 48 95 60 17 61 26 ...
output:
2946453946
result:
ok single line: '2946453946'
Test #7:
score: 10
Accepted
time: 155ms
memory: 22712kb
input:
500000 -3 6000 -500000 68 30 8 100 90 57 94 23 23 91 52 83 31 78 39 4 76 11 60 42 34 50 59 57 5 5 79 74 59 48 11 60 98 76 79 43 37 34 78 20 66 67 54 93 76 78 70 42 2 25 31 4 84 91 67 9 20 46 2 29 40 20 37 39 1 68 16 3 44 38 78 86 28 71 40 6 3 22 58 96 25 25 9 43 49 72 14 99 11 90 49 82 82 82 17 85 7...
output:
89537932739
result:
ok single line: '89537932739'
Test #8:
score: 10
Accepted
time: 256ms
memory: 34352kb
input:
800000 -1 12000 -30000000 16 53 4 96 38 47 74 96 94 42 54 77 49 42 59 87 56 2 94 67 17 64 77 10 93 56 28 50 53 85 85 1 12 67 29 58 37 34 7 56 65 40 64 64 40 73 20 27 28 92 56 88 66 19 52 10 80 31 20 85 99 77 41 62 50 16 17 40 79 19 99 74 48 18 95 78 100 48 34 54 35 80 21 89 43 65 3 96 24 33 52 95 39...
output:
42188644308
result:
ok single line: '42188644308'
Test #9:
score: 10
Accepted
time: 315ms
memory: 42028kb
input:
1000000 -1 9000 -16000000 25 30 52 90 93 83 35 52 100 5 84 6 99 66 4 81 71 79 34 43 37 12 77 1 19 63 10 5 60 5 41 5 44 21 84 88 50 94 22 30 81 99 57 14 12 81 59 9 53 46 39 88 77 27 99 6 18 67 36 73 88 65 68 82 72 42 59 99 38 40 61 88 30 2 35 88 38 41 96 65 86 66 74 70 80 98 69 84 8 54 3 19 34 6 64 7...
output:
50474087414
result:
ok single line: '50474087414'
Test #10:
score: 10
Accepted
time: 322ms
memory: 42016kb
input:
1000000 -2 10000 -6000000 35 74 95 59 82 69 27 94 29 57 73 89 86 61 20 20 93 21 82 93 16 25 71 20 20 72 9 11 11 73 33 56 35 37 5 67 74 10 18 42 72 24 20 66 87 31 36 64 37 40 48 60 19 47 57 41 43 20 54 72 15 52 56 69 92 98 74 28 98 71 57 4 78 31 27 26 68 85 29 100 55 93 57 4 73 4 3 18 27 28 26 96 95 ...
output:
155037593776
result:
ok single line: '155037593776'