PKU 3547 Cube evolvent
http://poj.org/problem?id=3547
n*mの数字の書かれたマスが与えられる。
この中から、立方体の展開図になるような6個の隣接したマスを選ぶときに、そのマスに書かれた数字の和の最大値を求めろというような問題。
展開図を配列につっこんで回転などをさせて、愚直に計算。
WAラッシュを覚悟したけれど一発で通ったので、嬉しかったです。
PI open[][6]={{mp(0,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(0,2)}, {mp(0,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(1,2)}, {mp(0,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(2,2)}, {mp(0,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(3,2)}, {mp(1,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(1,2)}, {mp(1,0),mp(0,1),mp(1,1),mp(2,1),mp(3,1),mp(2,2)}, {mp(0,0),mp(1,0),mp(2,0),mp(2,1),mp(3,1),mp(4,1)}, {mp(0,0),mp(1,0),mp(1,1),mp(1,2),mp(2,1),mp(3,1)}, {mp(0,0),mp(1,0),mp(1,1),mp(2,2),mp(2,1),mp(3,1)}, {mp(0,0),mp(1,0),mp(1,1),mp(3,2),mp(2,1),mp(3,1)}, {mp(0,0),mp(1,0),mp(1,1),mp(3,2),mp(2,1),mp(2,2)}, }; int in[100][100]; int tx[]={1,1,-1,-1}; int ty[]={1,-1,1,-1}; main(){ int n,m; cin>>n>>m; rep(i,n)rep(j,m)cin>>in[i][j]; int ans=0; rep(i,n){ rep(j,m){ int ten=2; while(ten--){ rep(k,11){ rep(l,4){ int tans=0; bool ok=true; rep(o,6){ int x=i+open[k][o].F*tx[l],y=j+open[k][o].S*ty[l]; if(x<0 || n<=x || y<0 || m<=y){ ok=false; break; } tans+=in[x][y]; } if(ok)ans=max(ans,tans); } } rep(k,11)rep(l,6)open[k][l]=mp(open[k][l].S,open[k][l].F); } } } cout<<ans<<endl; }