QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #559517 | #8218. 水镜 | Ayaya | 17 | 250ms | 22876kb | C++14 | 1.5kb | 2024-09-11 22:47:05 | 2024-09-11 22:47:06 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<unordered_map>
#include<vector>
#include<bitset>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<numeric>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define lc (x<<1)
#define rc (x<<1|1)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int Mx=5005,p=998244353;
int read(){
char ch=getchar();
int Alice=0,Aya=1;
while(ch<'0'||ch>'9'){
if(ch=='-') Aya=-Aya;
ch=getchar();
}
while(ch>='0'&&ch<='9')
Alice=(Alice<<3)+(Alice<<1)+(ch^48),ch=getchar();
return (Aya==1?Alice:-Alice);
}
int n;
int a[Mx];
int b[Mx];
int ans;
bool vis[Mx][Mx];
int Calc(int k){
for(int i=1;i<=n;i++){
b[i]=k-a[i];
}
int res=0;
for(int l=1;l<=n;l++){
int mx=min(a[l],b[l]);
for(int r=l+1;r<=n;r++){
if(max(a[r],b[r])<=mx) break;
if(min(a[r],b[r])>mx) mx=min(a[r],b[r]);
else mx=max(a[r],b[r]);
res+=(!vis[l][r]);
vis[l][r]=1;
}
}
//cout<<k<<" : "<<res<<endl;
return res;
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read()<<1;
vector<int>vec;
for(int i=1;i<n;i++) vec.push_back(a[i]+a[i+1]+1),vec.push_back(a[i]+a[i+1]-1);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int k:vec){
ans+=Calc(k);
}
cout<<ans;
return 0;
}
/*
Hello!!
Sample:
-------------------
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 3768kb
input:
2 2 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
10 2 2 2 2 1 4 5 3 3 2
output:
20
result:
ok 1 number(s): "20"
Test #3:
score: 7
Accepted
time: 0ms
memory: 3528kb
input:
10 2 2 1 2 2 2 1 4 1 4
output:
17
result:
ok 1 number(s): "17"
Test #4:
score: 7
Accepted
time: 0ms
memory: 3856kb
input:
10 1 5 2 2 5 4 4 4 1 3
output:
20
result:
ok 1 number(s): "20"
Test #5:
score: 7
Accepted
time: 0ms
memory: 3596kb
input:
10 904418845477 67070474418 839309493679 528132965435 512894488193 602880026087 180594485896 804608714469 235337679831 584564033737
output:
33
result:
ok 1 number(s): "33"
Test #6:
score: 7
Accepted
time: 0ms
memory: 3528kb
input:
10 2550179579 103777915839 144714526810 113623620429 670640709602 630479108288 925117980861 409440663027 851501568790 70823805701
output:
24
result:
ok 1 number(s): "24"
Test #7:
score: 7
Accepted
time: 0ms
memory: 3596kb
input:
10 814733530324 125370066936 893046741545 865528217532 707538863565 13490262680 251316040999 984630720558 697932598323 635301702897
output:
28
result:
ok 1 number(s): "28"
Test #8:
score: 7
Accepted
time: 0ms
memory: 3788kb
input:
10 501904615091 622412193418 211917353535 453793869542 275851842760 930019650158 919242753532 856846287041 5971781899 267788891712
output:
25
result:
ok 1 number(s): "25"
Test #9:
score: 7
Accepted
time: 0ms
memory: 3656kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
45
result:
ok 1 number(s): "45"
Test #10:
score: 7
Accepted
time: 0ms
memory: 3528kb
input:
10 1 9 3 7 5 5 7 3 9 1
output:
45
result:
ok 1 number(s): "45"
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 10
Accepted
time: 1ms
memory: 3960kb
input:
100 19 17 1 6 13 14 4 2 10 18 14 13 15 6 11 20 3 4 12 13 16 12 19 20 12 15 7 7 5 8 1 2 1 10 4 8 6 3 15 4 7 20 9 5 5 19 12 3 19 12 11 20 11 13 19 12 11 1 11 13 17 12 3 19 3 6 9 1 16 20 11 6 5 18 10 5 17 3 6 6 5 19 12 18 20 8 11 7 4 10 12 2 3 8 10 11 12 17 10 13
output:
355
result:
ok 1 number(s): "355"
Test #12:
score: 10
Accepted
time: 1ms
memory: 4044kb
input:
100 11 12 5 10 17 5 20 15 7 14 10 17 10 16 3 5 9 15 12 14 17 9 19 17 10 19 15 12 16 3 17 19 4 1 4 15 8 18 6 17 14 3 13 8 5 19 15 18 2 13 6 16 9 7 5 19 14 18 4 15 16 20 20 12 13 8 1 8 8 14 2 14 2 20 1 2 10 17 4 11 20 3 17 20 10 1 15 4 2 13 19 5 5 12 4 20 12 8 15 8
output:
329
result:
ok 1 number(s): "329"
Test #13:
score: 10
Accepted
time: 1ms
memory: 4024kb
input:
100 13 1 17 11 17 16 2 19 4 12 17 20 5 16 6 12 5 13 20 9 5 11 15 19 7 12 10 8 1 15 5 18 17 6 8 1 3 20 7 2 6 16 12 2 8 8 8 16 17 3 2 6 16 20 6 17 13 9 3 13 16 4 17 2 1 5 4 17 18 2 20 20 1 2 3 17 6 19 14 19 1 16 20 18 18 19 17 10 12 4 4 7 7 20 17 8 13 3 4 20
output:
341
result:
ok 1 number(s): "341"
Test #14:
score: 10
Accepted
time: 1ms
memory: 4152kb
input:
100 455034032423 840073096526 371978331570 246220724495 848266080019 398599858195 43353392382 756939578255 530589723334 821276803992 285109610982 824022204844 843046304891 457318460201 236280080327 993688181715 931000714927 74912651346 596930659390 108045930673 786721240608 113666298593 752565704488...
output:
354
result:
ok 1 number(s): "354"
Test #15:
score: 10
Accepted
time: 1ms
memory: 4028kb
input:
100 706803971842 182640873284 1704165072 559627509398 484557550955 871039370321 709588903929 114342552454 343333988500 86063001721 347866503882 979150837026 33449005086 596006888876 348253213830 278470599929 173232429803 645372479772 516922735020 377571307486 562805393179 861663200058 790855050750 6...
output:
361
result:
ok 1 number(s): "361"
Test #16:
score: 10
Accepted
time: 1ms
memory: 3892kb
input:
100 578347178210 496384619990 135128913638 147893161408 422688449638 282961943591 192069785806 802186030105 650299430253 535251843527 311843686390 580567317768 634055654658 757084218324 761730552459 492093332681 193384270450 950166815145 788896509179 36975514073 794198358860 808807619812 56979983205...
output:
368
result:
ok 1 number(s): "368"
Test #17:
score: 10
Accepted
time: 2ms
memory: 4068kb
input:
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
output:
4950
result:
ok 1 number(s): "4950"
Test #18:
score: 10
Accepted
time: 0ms
memory: 4044kb
input:
100 1 99 3 97 5 95 7 93 9 91 11 89 13 87 15 85 17 83 19 81 21 79 23 77 25 75 27 73 29 71 31 69 33 67 35 65 37 63 39 61 41 59 43 57 45 55 47 53 49 51 51 49 53 47 55 45 57 43 59 41 61 39 63 37 65 35 67 33 69 31 71 29 73 27 75 25 77 23 79 21 81 19 83 17 85 15 87 13 89 11 91 9 93 7 95 5 97 3 99 1
output:
4950
result:
ok 1 number(s): "4950"
Test #19:
score: 10
Accepted
time: 1ms
memory: 3940kb
input:
100 3331 3236 3393 3172 3455 3108 3517 3044 3579 2980 3641 2916 3703 2852 3765 2788 3827 2724 3889 2660 3951 2596 4013 2532 4075 2468 4137 2404 4199 2340 4261 2276 4323 2212 4385 2148 4447 2084 4509 2020 4571 1956 4633 1892 4695 1828 4757 1764 4819 1700 4881 1636 4943 1572 5005 1508 5067 1444 5129 1...
output:
4338
result:
ok 1 number(s): "4338"
Test #20:
score: 10
Accepted
time: 0ms
memory: 4180kb
input:
100 3331 3362 3393 3424 3455 3106 3517 3548 3010 3610 2945 2914 3703 2851 3765 3796 2756 3858 3889 2660 3951 2594 2563 4044 4075 4106 4137 4168 4199 2340 2309 2277 4323 2211 4385 4416 2116 4478 2053 4540 4571 4602 4633 4664 1862 4726 1799 4788 1735 4850 1673 1642 4943 4974 1544 1511 5067 1446 1414 1...
output:
4477
result:
ok 1 number(s): "4477"
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #21:
score: 18
Accepted
time: 3ms
memory: 19756kb
input:
4000 59 57 11 30 50 26 22 40 22 30 52 30 49 16 44 12 59 49 3 63 49 39 10 33 57 61 28 46 52 27 61 62 38 40 47 53 47 35 29 3 33 12 42 25 52 7 16 27 27 19 43 16 44 39 31 59 39 17 11 41 36 2 57 41 51 47 53 61 9 43 37 52 29 4 27 55 51 56 32 31 58 12 54 18 57 26 48 60 23 59 59 39 59 32 21 35 10 42 34 13 1...
output:
15042
result:
ok 1 number(s): "15042"
Test #22:
score: 18
Accepted
time: 4ms
memory: 19716kb
input:
4000 54 11 2 3 60 33 33 37 45 46 59 43 52 51 60 39 10 34 24 39 31 28 32 25 30 52 35 34 45 53 46 5 51 32 7 42 2 5 8 7 26 16 12 38 50 61 27 57 36 43 57 40 9 2 40 17 55 12 39 1 51 30 3 9 18 27 32 25 1 45 11 63 33 8 59 58 26 30 50 48 31 37 52 48 29 63 46 16 20 17 21 10 26 50 23 58 54 45 20 47 20 34 27 2...
output:
14920
result:
ok 1 number(s): "14920"
Test #23:
score: 18
Accepted
time: 4ms
memory: 19816kb
input:
4000 38 27 24 16 61 3 31 40 2 44 32 34 39 5 52 11 15 49 50 37 39 13 28 13 49 53 52 42 2 35 47 30 6 55 37 21 18 49 49 9 16 2 15 29 10 37 8 9 30 63 63 7 5 5 33 29 45 40 36 44 19 58 62 6 35 18 13 45 28 5 19 6 55 22 46 30 24 53 9 51 39 53 36 6 57 58 44 25 7 45 37 19 51 60 57 34 49 46 60 32 41 14 28 36 5...
output:
14960
result:
ok 1 number(s): "14960"
Test #24:
score: 18
Accepted
time: 250ms
memory: 19836kb
input:
4000 12069940350 693104393746 506004291454 220881550815 702796548240 563007838282 611566604688 378666673738 610025585328 608894988649 124526215924 814019978312 897059164343 796219005720 524024478245 718000952354 602075499968 298585296960 543328090843 316577706850 261388159522 582026855690 7628473973...
output:
15294
result:
ok 1 number(s): "15294"
Test #25:
score: 18
Accepted
time: 238ms
memory: 19956kb
input:
4000 545602452568 885359959483 871445731617 402539507349 969870189205 715535779516 679089866142 819619714548 537112303865 94111574035 147483202998 474590238085 723316187067 923712967626 730257698370 944029734387 616538207318 592990174505 787329300826 732431878438 365002424706 663592470714 7733759852...
output:
15209
result:
ok 1 number(s): "15209"
Test #26:
score: 18
Accepted
time: 20ms
memory: 22876kb
input:
4000 1 3999 3 3997 5 3995 7 3993 9 3991 11 3989 13 3987 15 3985 17 3983 19 3981 21 3979 23 3977 25 3975 27 3973 29 3971 31 3969 33 3967 35 3965 37 3963 39 3961 41 3959 43 3957 45 3955 47 3953 49 3951 51 3949 53 3947 55 3945 57 3943 59 3941 61 3939 63 3937 65 3935 67 3933 69 3931 71 3929 73 3927 75 3...
output:
7998000
result:
ok 1 number(s): "7998000"
Test #27:
score: 0
Time Limit Exceeded
input:
4000 4000998 3998002 4002994 3996004 4004990 3994006 4006986 3992008 4008982 3990010 4010978 3988012 4012974 3986014 4014970 3984016 4016966 3982018 4018962 3980020 4020958 3978022 4022954 3976024 4024950 3974026 4026946 3972028 4028942 3970030 4030938 3968032 4032934 3966034 4034930 3964036 4036926...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%