QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149627 | #5480. New Year Festival | lgvc | TL | 6589ms | 717172kb | C++23 | 3.6kb | 2023-08-24 23:49:35 | 2023-08-24 23:49:38 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define eps 0.00000001
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
*pp++=ch;
}
inline void pcc(){
fwrite(buf2,1,pp-buf2,stdout);
pp=buf2;
}
inline int read(void){
int w=1;
register int x(0);register char c(getchar());
while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w*x;
}
void write(int x){
static int sta[20];
int top=0;
do{
sta[top++]=x%10,x/=10;
}while(x);
while(top) pc(sta[--top]+48);
}
void we(int x){
write(x);
pc('\n');
}
struct n_t{
int x,y;
};
inline bool cmp(n_t m,n_t n) {
return m.x<n.x;
}
int N,s[15],l[15],f[15],p[15],q[15],x[15][70],y[15][70],vi[23000009],as=INF_LL;
std::vector<n_t> dp,dq,stt[23000009];
inline int qr(int x) {
if(x>dq[dq.size()-1].x) return dq[dq.size()-1].y;
if(dq.size()==1) return dq[0].y;
int l=0,r=dq.size()-2,md;
while(l<r) {
md=(l+r+1)>>1;
if(x>=dq[md].x) l=md;else r=md-1;
}
return dq[l].y+(dq[l+1].y-dq[l].y)/(dq[l+1].x-dq[l].x)*(x-dq[l].x);
}
std::vector<n_t> ff(int xx) {
dp.clear();
dq.clear();
dp.push_back((n_t){0,0});
dp.push_back((n_t){100000000,0});
int vq=0;
for(int i=1;i<=xx;i++) {
vq=vq*N+f[i];
if(i<=7&&vi[vq]) {
dp=stt[vq];
if(dp.empty()) return dp;
continue;
}
dq=dp;
for(int j=1;j<=s[f[i]];j++) {
if(x[f[i]][j]>=dq[0].x) dp.push_back((n_t){x[f[i]][j],qr(x[f[i]][j])});
}
dq.clear();
std::sort(dp.begin(),dp.end(),cmp);
for(int j=0;j<dp.size();j++) if(dp[j].x<=x[f[i]][s[f[i]]]&&dp[j].x>=x[f[i]][1]) dq.push_back(dp[j]);
int st=1;
for(int j=0;j<dq.size();j++) {
while(st+1<s[f[i]]&&dq[j].x>=x[f[i]][st+1]) st++;
if(s[f[i]]==1) dq[j].y+=y[f[i]][1];
else dq[j].y+=y[f[i]][st]+(y[f[i]][st+1]-y[f[i]][st])/(x[f[i]][st+1]-x[f[i]][st])*(dq[j].x-x[f[i]][st]);
dq[j].x+=l[f[i]];
}
if(dq.empty()) {
if(i<=7) vi[vq]=1;
return dq;
}
dp.clear();
dp.push_back(dq[0]);
for(int j=1;j<dq.size();j++) {
if(dq[j].x!=dq[j-1].x) {
if(dp.size()) dq[j].y=std::min(dq[j].y,dp[dp.size()-1].y);
if(dp.size()>1&&(dp[dp.size()-2].y-dp[dp.size()-1].y)/(dp[dp.size()-2].x-dp[dp.size()-1].x)==
(dp[dp.size()-1].y-dq[j].y)/(dp[dp.size()-1].x-dq[j].x)) dp[dp.size()-1]=dq[j];
else dp.push_back(dq[j]);
}
}
if(i<=7) {
vi[vq]=1;
stt[vq]=dp;
}
}
return dp;
}
inline void tryy(int x) {
int k=0,ct=1;
for(int i=1;i<=N;i++) if((x>>i-1)&1) p[++k]=i,q[k]=k-1;
for(int i=1;i<=k;i++) ct=ct*i;
while(ct--) {
for(int i=1;i<=k;i++) f[i]=p[q[i]+1];
dq=ff(k);
if(!dq.empty()) as=std::min(as,dq[dq.size()-1].y);
std::next_permutation(q+1,q+k+1);
}
}
signed main(void) {
//freopen("m.in","r",stdin);
//freopen("m.out","w",stdout);
N=read();
for(int i=1;i<=N;i++) {
s[i]=read();l[i]=read();
for(int j=1;j<=s[i];j++) {
x[i][j]=read();
y[i][j]=read();
}
}
srand(time(NULL));
tryy((1<<N)-1);
printf("%lld\n",as);
/* int s=N/2;
for(int i=0;i<(1<<N);i++) {
if(__builtin_popcount(i)!=s) continue;
tryy(i);
}
if(N%2==1) {
for(int i=0;i<(1<<N);i++) {
if(__builtin_popcount(i)!=s+1) continue;
tryy(i);
}
}*/
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 60ms
memory: 543424kb
input:
3 3 50 300 2500 350 0 400 3000 2 120 380 0 400 2400 4 160 0 800 400 0 450 100 950 4600
output:
1460
result:
ok single line: '1460'
Test #2:
score: 0
Accepted
time: 68ms
memory: 544364kb
input:
4 2 160 384 0 1000 2464 3 280 0 2646 441 0 1000 2795 1 160 544 0 2 240 720 0 1220 2000
output:
2022
result:
ok single line: '2022'
Test #3:
score: 0
Accepted
time: 3715ms
memory: 689864kb
input:
11 6 192168 0 8547618 626988 33627138 706274 36560720 1103426 50858192 1399013 55291997 1418093 55559117 6 161415 0 58611901 321482 57647455 349707 57534555 550744 55524185 885629 50500910 1448846 27972230 6 195811 0 6825079 56106 8339941 78686 8836701 323216 12993711 525834 15627745 1414450 2095944...
output:
629407685
result:
ok single line: '629407685'
Test #4:
score: 0
Accepted
time: 4013ms
memory: 694328kb
input:
11 6 179446 0 62171637 917478 60336681 1352062 59032929 1368160 58566087 1370260 58503087 1473445 54375687 6 186773 0 2933427 20897 3748410 356883 13827990 1190424 27998187 1340354 29497487 1466118 29623251 6 185925 0 53735520 130212 51652128 582223 42611908 1090981 31419232 1380019 23326168 1466966...
output:
593944734
result:
ok single line: '593944734'
Test #5:
score: 0
Accepted
time: 3826ms
memory: 694488kb
input:
11 6 187590 0 512536 451768 16324416 582142 19714140 1060264 31667190 1212260 33491142 1463556 33742438 6 186786 0 39848792 254907 39084071 928124 31678684 1344556 21684316 1452774 18978866 1464360 18619700 6 177523 0 42981626 30401 42920824 495821 40593724 949343 37419070 1207056 33295662 1473623 2...
output:
568541879
result:
ok single line: '568541879'
Test #6:
score: 0
Accepted
time: 2580ms
memory: 639664kb
input:
11 6 180328 0 70912449 593492 69725465 631349 69119753 934610 63357794 1254206 51852338 1281827 50747498 2 1 543152 90245567 543162 90245567 6 176608 0 46706614 512238 65147182 604236 67263136 771264 69935584 987683 71666936 1285547 72858392 6 169123 0 71973961 349057 70228676 742671 63930852 106384...
output:
728555275
result:
ok single line: '728555275'
Test #7:
score: 0
Accepted
time: 2515ms
memory: 634004kb
input:
11 6 171004 0 62863146 53160 62703666 297997 60500133 928595 50410565 1047846 48383298 1196274 42891462 2 1 497649 90358616 497658 90358616 2 1 877017 61053965 877067 61053965 6 192851 0 73730741 188629 73542112 238857 72939376 589071 62432956 903490 52685967 1174427 43474109 6 165034 0 39275349 288...
output:
684905214
result:
ok single line: '684905214'
Test #8:
score: 0
Accepted
time: 2497ms
memory: 632940kb
input:
11 6 170701 0 66082360 363625 79900110 500001 84400518 1033901 98815818 1139446 99237998 1267187 99493480 2 1 529976 58976463 530026 58976463 6 199596 0 39595850 278702 34857916 365221 32781460 531968 28112544 917360 15009216 1238292 3455664 2 1 729627 23545904 729649 23545904 6 195425 0 21131820 63...
output:
539418869
result:
ok single line: '539418869'
Test #9:
score: 0
Accepted
time: 2455ms
memory: 631012kb
input:
11 2 1 731822 57736604 731847 57736604 6 177906 0 31265048 204117 29632112 367764 26686466 1053673 12282377 1153199 9694701 1266786 6059917 2 1 536410 26155530 536462 26155530 2 1 920218 89157371 920236 89157371 6 173499 0 5971470 368364 19969302 688960 30869566 1086522 43989112 1098619 44364119 127...
output:
615248718
result:
ok single line: '615248718'
Test #10:
score: 0
Accepted
time: 2471ms
memory: 633080kb
input:
11 6 196632 0 70110348 384388 82026376 394546 82199062 763377 86993865 810963 87422139 1260374 90118605 2 1 933046 16939393 933100 16939393 6 173665 0 25812347 235451 34524034 294814 36661102 403393 40352788 999221 58227628 1283341 59648228 6 177710 0 58412603 233394 55145087 426572 50122459 430534 ...
output:
735311761
result:
ok single line: '735311761'
Test #11:
score: 0
Accepted
time: 1869ms
memory: 593412kb
input:
11 2 1 327714 97173804 327766 97173804 6 174068 0 97264397 26713 97130832 179562 95143795 858948 81556075 987929 78460531 1015941 77704207 6 175212 0 64880924 252642 73976036 266800 74400776 390959 77132274 806405 81286734 1014797 82953870 6 163249 0 42044695 49476 41747839 197386 40120829 451676 35...
output:
558987902
result:
ok single line: '558987902'
Test #12:
score: 0
Accepted
time: 1943ms
memory: 592332kb
input:
11 6 163829 0 31289574 130497 30376095 712717 16402815 753079 15232317 797225 13907937 1066319 3144177 6 168138 0 63124751 45649 64585519 810233 88287623 898033 90658223 905417 90842823 1062010 91312602 6 170025 0 53069325 321981 48561591 591234 41291760 942888 31093794 1024294 28488802 1060123 2705...
output:
569257965
result:
ok single line: '569257965'
Test #13:
score: 0
Accepted
time: 1914ms
memory: 592912kb
input:
11 6 167138 0 51023002 165600 56984602 219698 58878032 339095 61146575 892576 71109233 1041644 72748981 2 1 689176 94343012 689249 94343012 6 178942 0 58650734 374 58663824 515755 76186778 947018 84812038 988564 85559866 1029840 85724970 6 173405 0 47201281 229648 55468609 308300 57434909 384679 588...
output:
675590982
result:
ok single line: '675590982'
Test #14:
score: 0
Accepted
time: 1866ms
memory: 592932kb
input:
11 6 174305 0 94317116 156381 93066068 738860 83163925 801318 81914765 1058316 74461823 1076858 73738685 6 187492 0 57378030 357720 70255950 383079 70940643 538696 74519834 830802 80946166 1063671 84439201 6 179318 0 62479756 269535 70565806 281413 70874634 634924 74763255 916720 75608643 1071845 75...
output:
712616989
result:
ok single line: '712616989'
Test #15:
score: 0
Accepted
time: 1863ms
memory: 594136kb
input:
11 6 181795 0 17122556 102744 21129572 299317 28009627 806065 45239059 921763 47553019 1095305 48420729 6 190533 0 42602682 10275 43003407 180188 48610536 865763 67806636 939173 69715296 1086567 71631418 2 1 529036 58707251 529083 58707251 2 1 917587 10593491 917630 10593491 6 166172 0 73743543 1369...
output:
542369675
result:
ok single line: '542369675'
Test #16:
score: 0
Accepted
time: 1539ms
memory: 566820kb
input:
11 2 1 727800 20498697 727829 20498697 6 177706 0 21250146 38893 21133467 250783 20285907 792887 8359619 798142 8191459 884652 5163609 6 162623 0 14906340 379619 30091100 415655 31424432 559643 35888060 746934 39821171 899735 42571589 6 179608 0 11941388 203734 19479546 321997 23263962 444492 265713...
output:
432748635
result:
ok single line: '432748635'
Test #17:
score: 0
Accepted
time: 1539ms
memory: 564372kb
input:
11 2 1 331882 64233485 331943 64233485 6 161328 0 26996144 322377 22805243 707171 16648539 771738 15357199 776897 15248860 867217 12448940 2 1 867971 91310630 867989 91310630 6 160555 0 78199529 86753 80715366 401127 88574716 504487 90848636 790264 95135291 867990 95290743 2 1 703673 27828123 703687...
output:
683878583
result:
ok single line: '683878583'
Test #18:
score: 0
Accepted
time: 1572ms
memory: 564184kb
input:
11 6 174316 0 47897162 641806 72927596 644242 73010420 755581 76016573 811250 76628932 893211 76792854 6 166188 0 66549903 71840 66406223 119861 65877992 325611 62791742 616567 54644974 901339 44393182 6 165579 0 1031241 48042 2760753 196253 5724973 535978 10820848 581549 11003132 901948 11964329 2 ...
output:
619086324
result:
ok single line: '619086324'
Test #19:
score: 0
Accepted
time: 1571ms
memory: 566468kb
input:
11 6 167704 0 58832679 370569 55868127 626169 53567727 663624 52781172 836807 47412499 898647 45309939 6 178808 0 88894906 243375 88164781 297907 87946653 335037 87315443 849159 75490637 887543 74032045 2 1 730898 45305194 730922 45305194 2 1 167710 57873219 167770 57873219 2 1 346582 81704091 34665...
output:
584549217
result:
ok single line: '584549217'
Test #20:
score: 0
Accepted
time: 1573ms
memory: 566088kb
input:
11 6 172855 0 42531672 172560 42186552 638982 36123066 740826 34697250 880888 31896010 912058 30960910 2 1 172859 87907354 172901 87907354 2 1 913759 84347576 913770 84347576 2 1 737496 15253290 737524 15253290 2 1 550983 60643609 551035 60643609 6 194108 0 64902863 18457 64810578 217247 61431148 54...
output:
597390225
result:
ok single line: '597390225'
Test #21:
score: 0
Accepted
time: 1166ms
memory: 544924kb
input:
11 2 1 531 70843885 615 70843885 2 1 343 58517596 443 58517596 2 1 215 65255473 306 65255473 2 1 1 85022551 78 85022551 2 1 308 25241720 339 25241720 2 1 451 26840810 529 26840810 2 1 209 65672580 210 65672580 2 1 658 10786993 725 10786993 2 1 139 59113224 207 59113224 2 1 88 31479467 130 31479467 2...
output:
529410596
result:
ok single line: '529410596'
Test #22:
score: 0
Accepted
time: 1241ms
memory: 545244kb
input:
11 3 10 11 10000000 12 0 13 10000000 3 20 21 10000000 22 0 23 10000000 3 40 41 10000000 42 0 43 10000000 3 80 81 10000000 82 0 83 10000000 3 160 161 10000000 162 0 163 10000000 3 320 321 10000000 322 0 323 10000000 3 640 641 10000000 642 0 643 10000000 3 1280 1281 10000000 1282 0 1283 10000000 3 256...
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 6589ms
memory: 717172kb
input:
11 3 100000 100100 10000000 100101 0 100102 10000000 4 1 99999 10000000 100000 101022 201022 0 201023 10000000 4 2 99999 10000000 100000 0 201021 101021 201022 10000000 4 4 99999 10000000 100000 101019 201019 0 201020 10000000 4 8 99999 10000000 100000 0 201015 101015 201016 10000000 4 16 99999 1000...
output:
1004939
result:
ok single line: '1004939'
Test #24:
score: 0
Accepted
time: 4529ms
memory: 699240kb
input:
11 1 1 309 0 2 1 0 1023 1023 0 2 2 0 0 1022 1022 2 4 0 1020 1020 0 2 8 0 1016 1016 0 2 16 0 0 1008 1008 2 32 0 0 992 992 2 64 0 0 960 960 2 128 0 0 896 896 2 256 0 768 768 0 2 512 0 0 512 512
output:
3669
result:
ok single line: '3669'
Test #25:
score: 0
Accepted
time: 67ms
memory: 543684kb
input:
5 5 14740 0 98138440 83236395 98138440 83236396 35898835 83236397 98138440 100000000 98138440 5 18569 0 69878160 42264949 69878160 42264950 68129173 42264951 69878160 100000000 69878160 5 63770 0 65429428 25122042 65429428 25122043 24329432 25122044 65429428 100000000 65429428 5 92572 0 96131514 801...
output:
234464013
result:
ok single line: '234464013'
Test #26:
score: -100
Time Limit Exceeded
input:
11 5 89 0 84080533 74506841 84080533 74506842 83055856 74506843 84080533 100000000 84080533 5 18029 0 68815953 58287635 68815953 58287636 31497588 58287637 68815953 100000000 68815953 5 7715 0 79502447 7136910 79502447 7136911 13979205 7136912 79502447 100000000 79502447 5 11560 0 58769677 67015775 ...