Submission #48505

#	Time	Username	Problem	Language	Result	Execution time	Memory
48505		leehosu01	막대기 (KOI13_game)	C++17	0 / 100	1076 ms	8368 KiB

game

#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)<<28|(b&TT))<<10)|(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;});//가능한 뒤부터본다.

    for(i=0;i<N;i++)
        Eg[0][V[i].A].push_back(V[i].B);

    ll leng=0;
    for(i=0;i<Eg[0].size();i++)leng=max(leng,pro(i,-1,0));
    for(i=0;i<Eg[1].size();i++)leng=max(leng,pro(-1,i,1));
    printf("%lld",leng);
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:71:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<Eg[0].size();i++)leng=max(leng,pro(i,-1,0));
             ~^~~~~~~~~~~~~
game.cpp:72:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<Eg[1].size();i++)leng=max(leng,pro(-1,i,1));
             ~^~~~~~~~~~~~~
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);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 22
• Subtask 5: 0 / 38