結果
問題 | No.974 最後の日までに |
ユーザー |
|
提出日時 | 2020-05-29 05:51:12 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,157 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 33,152 KB |
実行使用メモリ | 25,476 KB |
最終ジャッジ日時 | 2024-10-13 23:30:13 |
合計ジャッジ時間 | 12,258 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 WA * 37 |
ソースコード
#include<stdio.h>#include<stdlib.h>#define size 524288//64#define dvd 26//3long 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+0long 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((i&1ll)==0){cd.cost-=p[0];}for(j=0;j<dvd-1;j++){if(i&(1ll<<j)){cd.score+=q[j+1];cd.cost+=r[j+1];}}for(j=0;j<dvd-1;j++){if((i&(1ll<<j))==0 && (i&(1ll<<(j+1)))==0){cd.cost-=p[j+1];}}if(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(i&(1ll<<j)){cd.score+=q[dvd+j+1];cd.cost+=r[dvd+j+1];}}for(j=0;j<dvd-1;j++){if((i&(1ll<<j))==0 && (i&(1ll<<(j+1)))==0){cd.cost-=p[dvd+j+1];}}if(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++){//fprintf(stderr,"%lld\n",fc[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;}