QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #103137 | #391. Commando | fzj2007 | 100 ✓ | 47ms | 81472kb | C++17 | 1.7kb | 2023-05-04 16:19:16 | 2023-05-04 16:19:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define int __int128
#define N 1000005
int n,A,B,C,w[N],f[N],X[N],Y[N];
int q[N];
signed main(){
read(n,A,B,C);
for(int i=1;i<=n;i++) read(w[i]),w[i]+=w[i-1];
int head=1,tail=0;
q[++tail]=0;
for(int i=1;i<=n;i++){
while(head<tail&&2ll*A*w[i]*(X[q[head+1]]-X[q[head]])<=Y[q[head+1]]-Y[q[head]]) head++;
f[i]=f[q[head]]+A*(w[i]-w[q[head]])*(w[i]-w[q[head]])+B*(w[i]-w[q[head]])+C,X[i]=w[i],Y[i]=f[i]+A*w[i]*w[i]-B*w[i];
while(head<tail&&(Y[i]-Y[q[tail-1]])*(X[q[tail]]-X[q[tail-1]])>=(Y[q[tail]]-Y[q[tail-1]])*(X[i]-X[q[tail-1]])) tail--;
q[++tail]=i;
}
put('\n',f[n]);
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 9512kb
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: 10
Accepted
time: 1ms
memory: 9520kb
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:
1588599
result:
ok single line: '1588599'
Test #3:
score: 10
Accepted
time: 0ms
memory: 11696kb
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: 4ms
memory: 9740kb
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: 2ms
memory: 11856kb
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: 9ms
memory: 18044kb
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: 30ms
memory: 50184kb
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: 40ms
memory: 72376kb
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: 40ms
memory: 81472kb
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: 47ms
memory: 81436kb
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'