結果
問題 | No.974 最後の日までに |
ユーザー | butsurizuki |
提出日時 | 2020-05-29 05:58:39 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 3,166 bytes |
コンパイル時間 | 929 ms |
コンパイル使用メモリ | 31,876 KB |
実行使用メモリ | 28,112 KB |
最終ジャッジ日時 | 2023-08-04 03:00:43 |
合計ジャッジ時間 | 15,964 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 213 ms
24,904 KB |
testcase_01 | AC | 253 ms
24,356 KB |
testcase_02 | AC | 250 ms
24,784 KB |
testcase_03 | AC | 257 ms
21,264 KB |
testcase_04 | AC | 253 ms
24,452 KB |
testcase_05 | AC | 254 ms
24,968 KB |
testcase_06 | AC | 252 ms
27,604 KB |
testcase_07 | AC | 252 ms
24,788 KB |
testcase_08 | AC | 252 ms
25,224 KB |
testcase_09 | AC | 248 ms
21,288 KB |
testcase_10 | AC | 245 ms
24,876 KB |
testcase_11 | AC | 244 ms
24,428 KB |
testcase_12 | AC | 249 ms
25,000 KB |
testcase_13 | AC | 249 ms
21,240 KB |
testcase_14 | AC | 248 ms
24,720 KB |
testcase_15 | AC | 246 ms
24,616 KB |
testcase_16 | AC | 243 ms
25,028 KB |
testcase_17 | AC | 225 ms
24,788 KB |
testcase_18 | AC | 232 ms
24,368 KB |
testcase_19 | AC | 231 ms
21,352 KB |
testcase_20 | AC | 230 ms
27,500 KB |
testcase_21 | AC | 227 ms
21,348 KB |
testcase_22 | AC | 226 ms
27,888 KB |
testcase_23 | AC | 228 ms
28,112 KB |
testcase_24 | AC | 226 ms
24,824 KB |
testcase_25 | AC | 217 ms
27,568 KB |
testcase_26 | AC | 219 ms
27,828 KB |
testcase_27 | AC | 259 ms
24,968 KB |
testcase_28 | AC | 268 ms
24,500 KB |
testcase_29 | AC | 192 ms
23,992 KB |
testcase_30 | AC | 242 ms
24,596 KB |
testcase_31 | AC | 192 ms
20,488 KB |
testcase_32 | AC | 190 ms
27,168 KB |
testcase_33 | AC | 261 ms
24,980 KB |
testcase_34 | AC | 263 ms
21,272 KB |
testcase_35 | AC | 201 ms
24,136 KB |
testcase_36 | AC | 197 ms
20,964 KB |
testcase_37 | AC | 245 ms
27,852 KB |
testcase_38 | AC | 191 ms
24,612 KB |
testcase_39 | AC | 197 ms
23,908 KB |
testcase_40 | AC | 234 ms
27,628 KB |
testcase_41 | AC | 234 ms
21,264 KB |
testcase_42 | AC | 247 ms
27,612 KB |
testcase_43 | AC | 247 ms
25,256 KB |
testcase_44 | AC | 247 ms
24,712 KB |
testcase_45 | AC | 245 ms
24,620 KB |
testcase_46 | AC | 205 ms
24,804 KB |
testcase_47 | AC | 206 ms
24,284 KB |
testcase_48 | AC | 207 ms
24,732 KB |
testcase_49 | AC | 195 ms
23,932 KB |
testcase_50 | AC | 200 ms
24,216 KB |
testcase_51 | AC | 198 ms
20,900 KB |
ソースコード
#include<stdio.h> #include<stdlib.h> #define size 524288 #define dvd 26 long long llmax(long long a,long long b){if(a>b){return a;}return b;} typedef struct{ long long score; long long cost; }sd; int sdsortfncsj(const void *a,const void *b){ if(((sd*)a)->cost < ((sd*)b)->cost){return -1;} if(((sd*)a)->cost > ((sd*)b)->cost){return 1;} return 0; } int sdsortfnckj(const void *a,const void *b){ if(((sd*)a)->cost > ((sd*)b)->cost){return -1;} if(((sd*)a)->cost < ((sd*)b)->cost){return 1;} return 0; } int main(){ long long i,j,c=0,fl,w,res=0; long long fmem[size]; sd fir[2][size],sec[2][size],cd; //fir[1...last==school] sec[1...first==school] //merge pattern : 1+0 0+1 0+0 long long fc[2]={0},sc[2]={0}; long long p[64]={0},q[64]={0},r[64]={0}; long long fp,sp; scanf("%lld",&w); for(i=0;i<w;i++){scanf("%lld%lld%lld",&p[i],&q[i],&r[i]);} w=2*dvd; i=0; while(i<(1ll<<dvd)){ fl=0; for(j=dvd-2;j>=0;j--){ if((i&(1ll<<(j+1)))!=0 && (i&(1ll<<j))!=0){ i+=(1ll<<j);fl=1; } } if(fl==1){continue;} fmem[c]=i; c++;i++; } for(i=0;i<c;i++){ cd.score=0; cd.cost=0; if((fmem[i]&1ll)==0){cd.cost-=p[0];} for(j=0;j<dvd-1;j++){ if(fmem[i]&(1ll<<j)){ cd.score+=q[j+1]; cd.cost+=r[j+1]; } } for(j=0;j<dvd-1;j++){ if((fmem[i]&(1ll<<j))==0 && (fmem[i]&(1ll<<(j+1)))==0){ cd.cost-=p[j+1]; } } if(fmem[i]&(1ll<<(dvd-1))){ fir[1][fc[1]]=cd;fc[1]++; } else{ fir[0][fc[0]]=cd;fc[0]++; } } for(i=0;i<c;i++){ cd.score=0; cd.cost=0; for(j=0;j<dvd;j++){ if(fmem[i]&(1ll<<j)){ cd.score+=q[dvd+j+1]; cd.cost+=r[dvd+j+1]; } } for(j=0;j<dvd-1;j++){ if((fmem[i]&(1ll<<j))==0 && (fmem[i]&(1ll<<(j+1)))==0){ cd.cost-=p[dvd+j+1]; } } if(fmem[i]&1ll){ sec[1][sc[1]]=cd;sc[1]++; } else{ sec[0][sc[0]]=cd;sc[0]++; } } //fprintf(stderr,"ok\n"); for(i=0;i<2;i++){ qsort(fir[i],fc[i],sizeof(fir[i][0]),sdsortfncsj); for(j=1;j<fc[i];j++){ fir[i][j].score=llmax(fir[i][j-1].score,fir[i][j].score); } //for(j=0;j<fc[i];j++){fprintf(stderr,"<%lld : %lld>\n",fir[i][j].cost,fir[i][j].score);} qsort(sec[i],sc[i],sizeof(sec[i][0]),sdsortfnckj); for(j=sc[i]-2;j>=0;j--){ sec[i][j].score=llmax(sec[i][j+1].score,sec[i][j].score); } //for(j=0;j<sc[i];j++){fprintf(stderr,"[%lld : %lld]\n",sec[i][j].cost,sec[i][j].score);} } //fprintf(stderr,"ok\n"); fp=0;sp=0; while(fp<fc[0] && sp<sc[1]){ if(fir[0][fp].cost+sec[1][sp].cost<=0){ res=llmax(fir[0][fp].score+sec[1][sp].score,res); fp++; } else{sp++;} } fp=0;sp=0; while(fp<fc[1] && sp<sc[0]){ if(fir[1][fp].cost+sec[0][sp].cost+r[dvd]<=0){ res=llmax(fir[1][fp].score+sec[0][sp].score+q[dvd],res); fp++; } else{sp++;} } fp=0;sp=0; while(fp<fc[0] && sp<sc[0]){ if(fir[0][fp].cost+sec[0][sp].cost-p[dvd]<=0){ res=llmax(fir[0][fp].score+sec[0][sp].score,res); fp++; } else{sp++;} } printf("%lld\n",res); return 0; }