| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 48504 |
2018-05-15T08:18:28 Z |
leehosu01 |
막대기 (KOI13_game) |
C++17 |
|
60 ms |
2892 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)<<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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
2636 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
2892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
