結果

問題 No.974 最後の日までに
ユーザー butsurizuki
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#include<stdlib.h>
#define size 524288//64
#define dvd 26//3
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((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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0