結果
問題 | No.974 最後の日までに |
ユーザー | butsurizuki |
提出日時 | 2020-05-29 05:58:39 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 3,166 bytes |
コンパイル時間 | 376 ms |
コンパイル使用メモリ | 34,156 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2024-04-22 01:29:42 |
合計ジャッジ時間 | 12,152 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 184 ms
17,284 KB |
testcase_01 | AC | 233 ms
17,156 KB |
testcase_02 | AC | 209 ms
17,304 KB |
testcase_03 | AC | 213 ms
17,156 KB |
testcase_04 | AC | 210 ms
17,156 KB |
testcase_05 | AC | 211 ms
17,284 KB |
testcase_06 | AC | 218 ms
17,280 KB |
testcase_07 | AC | 210 ms
17,284 KB |
testcase_08 | AC | 211 ms
17,156 KB |
testcase_09 | AC | 210 ms
17,284 KB |
testcase_10 | AC | 207 ms
17,288 KB |
testcase_11 | AC | 206 ms
17,156 KB |
testcase_12 | AC | 210 ms
17,280 KB |
testcase_13 | AC | 206 ms
17,408 KB |
testcase_14 | AC | 205 ms
17,284 KB |
testcase_15 | AC | 207 ms
17,280 KB |
testcase_16 | AC | 206 ms
17,280 KB |
testcase_17 | AC | 190 ms
17,284 KB |
testcase_18 | AC | 192 ms
17,280 KB |
testcase_19 | AC | 195 ms
17,304 KB |
testcase_20 | AC | 202 ms
17,280 KB |
testcase_21 | AC | 189 ms
17,280 KB |
testcase_22 | AC | 194 ms
17,288 KB |
testcase_23 | AC | 191 ms
17,292 KB |
testcase_24 | AC | 190 ms
17,280 KB |
testcase_25 | AC | 185 ms
17,280 KB |
testcase_26 | AC | 184 ms
17,280 KB |
testcase_27 | AC | 218 ms
17,280 KB |
testcase_28 | AC | 225 ms
17,284 KB |
testcase_29 | AC | 162 ms
16,640 KB |
testcase_30 | AC | 202 ms
17,156 KB |
testcase_31 | AC | 165 ms
16,640 KB |
testcase_32 | AC | 167 ms
16,640 KB |
testcase_33 | AC | 221 ms
17,284 KB |
testcase_34 | AC | 222 ms
17,280 KB |
testcase_35 | AC | 172 ms
17,152 KB |
testcase_36 | AC | 172 ms
16,896 KB |
testcase_37 | AC | 208 ms
17,284 KB |
testcase_38 | AC | 171 ms
16,640 KB |
testcase_39 | AC | 173 ms
17,024 KB |
testcase_40 | AC | 194 ms
17,284 KB |
testcase_41 | AC | 197 ms
17,304 KB |
testcase_42 | AC | 214 ms
17,408 KB |
testcase_43 | AC | 201 ms
17,280 KB |
testcase_44 | AC | 208 ms
17,280 KB |
testcase_45 | AC | 208 ms
17,284 KB |
testcase_46 | AC | 176 ms
17,024 KB |
testcase_47 | AC | 174 ms
17,152 KB |
testcase_48 | AC | 179 ms
17,152 KB |
testcase_49 | AC | 173 ms
17,024 KB |
testcase_50 | AC | 170 ms
17,024 KB |
testcase_51 | AC | 167 ms
17,024 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; }