QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149616 | #5480. New Year Festival | lgvc | TL | 5387ms | 95968kb | C++23 | 3.4kb | 2023-08-24 22:56:40 | 2023-08-24 22:56:40 |
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[2000009],as=INF_LL;
std::vector<n_t> dp,dq,stt[2000009];
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<=6&&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<=6) 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) dp.push_back(dq[j]);
}
for(int j=1;j<dp.size();j++) {
dp[j].y=std::min(dp[j].y,dp[j-1].y);
}
if(i<=6) {
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: 1ms
memory: 53264kb
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: 8ms
memory: 53460kb
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: 5085ms
memory: 94360kb
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: 5255ms
memory: 94300kb
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: 5387ms
memory: 95968kb
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: 3150ms
memory: 78632kb
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: 3018ms
memory: 77408kb
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: 3079ms
memory: 78348kb
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: 3062ms
memory: 77856kb
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: 3040ms
memory: 77016kb
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: 2098ms
memory: 66892kb
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: 2042ms
memory: 67448kb
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: 2182ms
memory: 67264kb
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: 2108ms
memory: 67424kb
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: 2026ms
memory: 67340kb
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: 1559ms
memory: 60232kb
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: 1558ms
memory: 60044kb
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: 1591ms
memory: 60136kb
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: 1656ms
memory: 60496kb
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: 1576ms
memory: 60052kb
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: 1085ms
memory: 54492kb
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: 1128ms
memory: 54160kb
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: -100
Time Limit Exceeded
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...