Submission #48504

#TimeUsernameProblemLanguageResultExecution timeMemory
48504leehosu01막대기 (KOI13_game)C++17
0 / 100
60 ms2892 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct E{ll A,B;}; vector<E>V; vector<vector<int> >Eg[2]; ll N,L,realX[2][100001]; map<ll,ll>MMP; inline ll buildup(ll a,ll b,ll c) { ll TT=(1<<18)-1; return (((a&TT)<<18|(b&TT))<<1)|(c&1); } ll pro(int m1,int m2,bool from) { if(MMP.find(buildup(m1,m2,from))!=MMP.end())return MMP[buildup(m1,m2,from)]; // printf(" %d %d %d\n",m1,m2,from); ll len=0; for(auto&I:Eg[from][(from==0?m1:m2)]) { // printf(" %d %d %d::%d\n",m1,m2,from,I); if(I<=(from==1?m1:m2))break; if(from==0) { // printf("%d %d %d::%lld %lld %lld::%lld \n",m1,m2,from,realX[!from][I],realX[from][m1],abs(realX[!from][I]-realX[from][m1]),pro(m1,I,!from)+L+abs(realX[!from][I]-realX[!from][m2])); len=max(len,pro(m1,I,!from)+L+abs(realX[!from][I]-realX[from][m1])); } if(from==1) { // printf("%d %d %d::%lld %lld %lld::%lld \n",m1,m2,from,realX[!from][I],realX[from][m2],abs(realX[!from][I]-realX[from][m2]),pro(I,m2,!from)+L+abs(realX[!from][I]-realX[!from][m1])); len=max(len,pro(I,m2,!from)+L+abs(realX[!from][I]-realX[from][m2])); } // printf("\n"); } // printf("len::%d %d %d::%lld\n",m1,m2,from,len); return MMP[buildup(m1,m2,from)]=len; } int main() { cin>>N>>L; V.resize(N); for(auto&I:V)scanf("%lld%lld",&I.A,&I.B); sort(V.begin(),V.end(),[](E&X,E&Y){return X.A==Y.A?X.B>Y.B:X.A<Y.A;});//가능한 뒤부터본다. ll cnt,i; for(cnt=0,i=0;i<N-1;i++) { realX[0][cnt]=V[i].A; V[i].A=(V[i].A!=V[i+1].A?cnt++:cnt); } V[i].A=cnt;realX[0][cnt]=V[i].A; Eg[0].resize(cnt+1); sort(V.begin(),V.end(),[](E&X,E&Y){return X.B==Y.B?X.A>Y.A:X.B<Y.B;});//가능한 뒤부터본다. for(cnt=0,i=0;i<N-1;i++) { realX[1][cnt]=V[i].B; // printf("%lld == %d\n",V[i].B,cnt); V[i].B=(V[i].B!=V[i+1].B?cnt++:cnt); } V[i].B=cnt;realX[1][cnt]=V[i].B; Eg[1].resize(cnt+1); for(i=0;i<N;i++)Eg[1][V[i].B].push_back(V[i].A);//,printf("%lld<==%lld\n",V[i].B,V[i].A); sort(V.begin(),V.end(),[](E&X,E&Y){return X.A==Y.A?X.B>Y.B:X.A<Y.A;});//가능한 뒤부터본다. int top1[100001],top2[100001]; memset(top1,0,sizeof top1); memset(top2,0,sizeof top2); for(i=0;i<N;i++) { Eg[0][V[i].A].push_back(V[i].B); ++top1[V[i].A]; ++top2[V[i].B]; } ll leng=0; for(i=0;i<Eg[0].size();i++) if(top1[i]==1) /*printf("%d %d %d \n",i,-1,0),*/leng=max(leng,pro(i,-1,0)); for(i=0;i<Eg[1].size();i++) if(top2[i]==1) /*printf("%d %d %d \n",-1,i,0),*/leng=max(leng,pro(-1,i,1)); printf("%lld",leng); }

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:78:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<Eg[0].size();i++)
             ~^~~~~~~~~~~~~
game.cpp:81:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<Eg[1].size();i++)
             ~^~~~~~~~~~~~~
game.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(auto&I:V)scanf("%lld%lld",&I.A,&I.B);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...