Submission #2172847
Source Code Expand
#include<cstdio> #include<utility> #include<set> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; long long arr[100002]; int l[100002],r[100002],n; set<pair<int,int> > se; inline void del(const int& a) { set<pair<int,int> >::iterator it; int b=l[a],c=r[a]; r[b]=c; l[c]=b; if(b>0) { it=se.find(make_pair(a-b,b)); if(it!=se.end()) { se.erase(it); } } if(c<=n) { it=se.find(make_pair(c-a,a)); if(it!=se.end()) { se.erase(it); } } if(b>0 && c<=n && (arr[b]>0)^(arr[c]>0)) { se.insert(make_pair(c-b,b)); } return; } int main() { int i,a,b,dis; long long x,ans,remain,rein; scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%I64d",&arr[i]); } remain=0; se.clear(); for(i=1;i<=n;++i) { scanf("%I64d",&x); arr[i]-=x; if(arr[i]<0) { remain-=arr[i]; } } for(i=1;i<=n;++i) { l[i]=i-1; r[i]=i+1; if( ((arr[i]>0)^(arr[i+1]>0)) && i<n) { se.insert(make_pair(1,i)); } } ans=0; while(remain) { // printf("%lld %d\n",remain,se.size()); dis=(se.begin())->first; a=(se.begin())->second; se.erase(se.begin()); b=r[a]; rein=min(abs(arr[a]),abs(arr[b])); remain-=rein; // printf("rein:%lld\n",rein); ans+=dis*rein; arr[a]+=(arr[a]>0?-rein:rein); arr[b]+=(arr[b]>0?-rein:rein); if(arr[a]==0) { del(a); } if(arr[b]==0) { del(b); } } printf("%I64d\n",ans); return 0; } /* 2 1 5 3 1 2 */ /* 5 1 2 3 4 5 3 3 1 1 1 6 */ /* 27 46 3 4 2 10 2 5 2 6 7 20 13 9 49 3 8 4 3 19 9 3 5 4 13 9 5 7 10 2 5 6 2 6 3 2 2 5 3 11 13 2 2 7 7 3 9 5 13 4 17 2 2 2 4 48 */ /* 18 3878348 423911 8031742 1035156 24256 10344593 19379 3867285 4481365 1475384 1959412 1383457 164869 4633165 6674637 9732852 10459147 2810788 1236501 770807 4003004 131688 1965412 266841 3980782 565060 816313 192940 541896 250801 217586 3806049 1220252 1161079 31168 2008961 6302172 */ /* 2 1 99999999999 1234567891 1 1234567890 */
Submission Info
Submission Time | |
---|---|
Task | H - WAAAAAAAAAAAAALL |
User | theyellowstar |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2038 Byte |
Status | WA |
Exec Time | 2103 ms |
Memory | 4096 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:46:24: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] scanf("%I64d",&arr[i]); ^ ./Main.cpp:52:19: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=] scanf("%I64d",&x); ^ ./Main.cpp:91:22: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=] printf("%I64d\n",ans); ^ ./Main.cpp:43:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:46:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%I64d",&arr[i]); ^ ./Main.cpp:52:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, de...
Judge Result
Set Name | Subtask1 | Subtask2 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 30 | 0 / 140 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt |
Subtask2 | 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt |
All | 00_00_sample.txt, 00_01_sample.txt, 00_02_sample.txt, 00_03_random.txt, 00_04_random.txt, 00_05_random.txt, 00_06_random.txt, 00_07_random.txt, 00_08_random.txt, 00_09_random.txt, 00_10_random.txt, 00_11_random.txt, 00_12_random.txt, 00_13_random.txt, 00_14_random.txt, 00_15_random.txt, 00_16_random.txt, 00_17_random.txt, 00_18_random.txt, 00_19_random.txt, 00_20_random.txt, 00_21_random.txt, 00_22_random.txt, 00_23_freedom.txt, 00_24_freedom.txt, 00_25_freedom.txt, 00_26_full.txt, 00_27_full.txt, 00_28_full.txt, 00_29_min.txt, 00_30_min.txt, 00_31_min.txt, 00_32_max.txt, 00_33_max.txt, 00_34_max.txt, 00_35_max.txt, 00_36_max.txt, 01_37_sample.txt, 01_38_sample.txt, 01_39_random.txt, 01_40_random.txt, 01_41_random.txt, 01_42_random.txt, 01_43_random.txt, 01_44_random.txt, 01_45_random.txt, 01_46_random.txt, 01_47_random.txt, 01_48_random.txt, 01_49_random.txt, 01_50_random.txt, 01_51_random.txt, 01_52_random.txt, 01_53_random.txt, 01_54_random.txt, 01_55_random.txt, 01_56_random.txt, 01_57_random.txt, 01_58_random.txt, 01_59_freedom.txt, 01_60_freedom.txt, 01_61_freedom.txt, 01_62_full.txt, 01_63_full.txt, 01_64_full.txt, 01_65_min.txt, 01_66_min.txt, 01_67_min.txt, 01_68_max.txt, 01_69_max.txt, 01_70_max.txt, 01_71_max.txt, 01_72_max.txt, 02_100_min.txt, 02_101_min.txt, 02_102_max.txt, 02_103_max.txt, 02_104_max.txt, 02_105_max.txt, 02_106_max.txt, 02_73_random.txt, 02_74_random.txt, 02_75_random.txt, 02_76_random.txt, 02_77_random.txt, 02_78_random.txt, 02_79_random.txt, 02_80_random.txt, 02_81_random.txt, 02_82_random.txt, 02_83_random.txt, 02_84_random.txt, 02_85_random.txt, 02_86_random.txt, 02_87_random.txt, 02_88_random.txt, 02_89_random.txt, 02_90_random.txt, 02_91_random.txt, 02_92_random.txt, 02_93_freedom.txt, 02_94_freedom.txt, 02_95_freedom.txt, 02_96_full.txt, 02_97_full.txt, 02_98_full.txt, 02_99_min.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_00_sample.txt | WA | 1 ms | 256 KB |
00_01_sample.txt | WA | 1 ms | 256 KB |
00_02_sample.txt | WA | 1 ms | 256 KB |
00_03_random.txt | WA | 1 ms | 256 KB |
00_04_random.txt | WA | 1 ms | 256 KB |
00_05_random.txt | WA | 1 ms | 256 KB |
00_06_random.txt | WA | 1 ms | 256 KB |
00_07_random.txt | WA | 1 ms | 256 KB |
00_08_random.txt | WA | 1 ms | 256 KB |
00_09_random.txt | WA | 1 ms | 256 KB |
00_10_random.txt | WA | 1 ms | 256 KB |
00_11_random.txt | WA | 1 ms | 256 KB |
00_12_random.txt | WA | 1 ms | 256 KB |
00_13_random.txt | WA | 1 ms | 256 KB |
00_14_random.txt | WA | 1 ms | 256 KB |
00_15_random.txt | WA | 1 ms | 256 KB |
00_16_random.txt | WA | 1 ms | 256 KB |
00_17_random.txt | WA | 1 ms | 256 KB |
00_18_random.txt | WA | 1 ms | 256 KB |
00_19_random.txt | WA | 1 ms | 256 KB |
00_20_random.txt | WA | 1 ms | 256 KB |
00_21_random.txt | WA | 1 ms | 256 KB |
00_22_random.txt | WA | 1 ms | 256 KB |
00_23_freedom.txt | WA | 1 ms | 256 KB |
00_24_freedom.txt | WA | 1 ms | 256 KB |
00_25_freedom.txt | WA | 1 ms | 256 KB |
00_26_full.txt | WA | 1 ms | 256 KB |
00_27_full.txt | WA | 1 ms | 256 KB |
00_28_full.txt | WA | 1 ms | 256 KB |
00_29_min.txt | WA | 1 ms | 256 KB |
00_30_min.txt | WA | 1 ms | 256 KB |
00_31_min.txt | WA | 1 ms | 256 KB |
00_32_max.txt | WA | 1 ms | 256 KB |
00_33_max.txt | WA | 1 ms | 256 KB |
00_34_max.txt | WA | 1 ms | 256 KB |
00_35_max.txt | WA | 1 ms | 256 KB |
00_36_max.txt | WA | 1 ms | 256 KB |
01_37_sample.txt | WA | 1 ms | 256 KB |
01_38_sample.txt | TLE | 2103 ms | 256 KB |
01_39_random.txt | WA | 2 ms | 256 KB |
01_40_random.txt | WA | 2 ms | 256 KB |
01_41_random.txt | WA | 2 ms | 256 KB |
01_42_random.txt | WA | 1 ms | 256 KB |
01_43_random.txt | WA | 1 ms | 256 KB |
01_44_random.txt | WA | 2 ms | 256 KB |
01_45_random.txt | WA | 1 ms | 256 KB |
01_46_random.txt | WA | 2 ms | 256 KB |
01_47_random.txt | WA | 1 ms | 256 KB |
01_48_random.txt | WA | 1 ms | 256 KB |
01_49_random.txt | WA | 2 ms | 256 KB |
01_50_random.txt | WA | 2 ms | 256 KB |
01_51_random.txt | WA | 1 ms | 256 KB |
01_52_random.txt | WA | 2 ms | 256 KB |
01_53_random.txt | WA | 2 ms | 256 KB |
01_54_random.txt | WA | 1 ms | 256 KB |
01_55_random.txt | WA | 2 ms | 256 KB |
01_56_random.txt | WA | 2 ms | 256 KB |
01_57_random.txt | WA | 2 ms | 256 KB |
01_58_random.txt | WA | 2 ms | 256 KB |
01_59_freedom.txt | WA | 1 ms | 256 KB |
01_60_freedom.txt | WA | 2 ms | 256 KB |
01_61_freedom.txt | WA | 2 ms | 256 KB |
01_62_full.txt | WA | 2 ms | 256 KB |
01_63_full.txt | TLE | 2103 ms | 256 KB |
01_64_full.txt | TLE | 2103 ms | 256 KB |
01_65_min.txt | TLE | 2103 ms | 256 KB |
01_66_min.txt | WA | 1 ms | 256 KB |
01_67_min.txt | TLE | 2103 ms | 256 KB |
01_68_max.txt | WA | 2 ms | 256 KB |
01_69_max.txt | WA | 2 ms | 256 KB |
01_70_max.txt | WA | 2 ms | 256 KB |
01_71_max.txt | WA | 2 ms | 256 KB |
01_72_max.txt | WA | 2 ms | 256 KB |
02_100_min.txt | WA | 1 ms | 256 KB |
02_101_min.txt | WA | 1 ms | 256 KB |
02_102_max.txt | WA | 115 ms | 4096 KB |
02_103_max.txt | WA | 122 ms | 4096 KB |
02_104_max.txt | WA | 124 ms | 4096 KB |
02_105_max.txt | WA | 101 ms | 3712 KB |
02_106_max.txt | WA | 109 ms | 3968 KB |
02_73_random.txt | WA | 82 ms | 3072 KB |
02_74_random.txt | WA | 106 ms | 4096 KB |
02_75_random.txt | WA | 61 ms | 2304 KB |
02_76_random.txt | WA | 89 ms | 3456 KB |
02_77_random.txt | WA | 41 ms | 1664 KB |
02_78_random.txt | WA | 90 ms | 3072 KB |
02_79_random.txt | WA | 26 ms | 1152 KB |
02_80_random.txt | WA | 120 ms | 3968 KB |
02_81_random.txt | WA | 95 ms | 3584 KB |
02_82_random.txt | WA | 76 ms | 2816 KB |
02_83_random.txt | WA | 43 ms | 1536 KB |
02_84_random.txt | WA | 53 ms | 2048 KB |
02_85_random.txt | WA | 80 ms | 2816 KB |
02_86_random.txt | WA | 90 ms | 3200 KB |
02_87_random.txt | WA | 25 ms | 896 KB |
02_88_random.txt | WA | 101 ms | 3712 KB |
02_89_random.txt | WA | 102 ms | 3968 KB |
02_90_random.txt | WA | 28 ms | 1280 KB |
02_91_random.txt | WA | 15 ms | 768 KB |
02_92_random.txt | WA | 57 ms | 2048 KB |
02_93_freedom.txt | WA | 49 ms | 1408 KB |
02_94_freedom.txt | WA | 26 ms | 896 KB |
02_95_freedom.txt | WA | 36 ms | 1152 KB |
02_96_full.txt | WA | 13 ms | 640 KB |
02_97_full.txt | WA | 104 ms | 3584 KB |
02_98_full.txt | WA | 95 ms | 3456 KB |
02_99_min.txt | TLE | 2103 ms | 256 KB |