oj.uz

Submission #48507

# Submission time Handle Problem Language Result Execution time Memory
48507 2018-05-15T08:27:50 Z leehosu01 막대기 (KOI13_game) C++17
0 / 100
 1000 ms 8224 KB 
#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;
}
ll pro2(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))continue;
        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,pro2(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,pro2(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));

    MMP.clear();

    for(i=0;i<Eg[0].size();i++)leng=max(leng,pro2(i,Eg[1].size(),0));
    for(i=0;i<Eg[1].size();i++)leng=max(leng,pro2(Eg[0].size(),i,1));



    printf("%lld",leng);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 8224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8224 KB Output is correct
2 Correct 5 ms 8224 KB Output is correct
3 Incorrect 124 ms 8224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8224 KB Output is correct
2 Correct 90 ms 8224 KB Output is correct
3 Execution timed out 1077 ms 8224 KB Time limit exceeded
4 Halted 0 ms 0 KB -