| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115671 |
2019-06-08T14:32:21 Z |
ckodser |
Robots (APIO13_robots) |
C++14 |
|
128 ms |
163840 KB |
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=610;
const ll inf=1e9+800;
const ll di[4]={-1,0 ,+1,0 };
const ll dj[4]={0 ,+1,0 ,-1};
ll w,h;
string s[maxn];
vector<pair<pii,ll> > out[maxn][maxn][4];
bool good[maxn][maxn][4];
vector<ll> inp[maxn*maxn];
ll dp[maxn*maxn][10][10];
inline ll getid(ll a,ll b){
return a*maxn+b;
}
ll chimishe(char s,ll d){
if(s=='C'){
d=(d+1)%4;
}if(s=='A'){
d=(d+3)%4;
}return d;
}
pair<pii,ll> movein(ll i,ll j,ll d){
i+=di[d];
j+=dj[d];
if(i<0 || i>=h || j<0 || j>=w || s[i][j]=='x'){
i-=di[d];
j-=dj[d];
}
return mp(mp(i,j),d);
}
void dfs(ll i,ll j,ll d,ll c){
if(getid(i,j)!=c)
inp[getid(i,j)].pb(c);
for(auto e:out[i][j][d]){
dfs(e.F.F,e.F.S,e.S,c);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
cin>>n>>w>>h;
for(ll i=0;i<h;i++){
cin>>s[i];
}
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
if('1'<=s[i][j] && s[i][j]<='9'){
s[i][j]-='1';
}
}
}
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
if(s[i][j]!='x'){
for(ll d=0;d<4;d++){
pair<pii,ll> e=movein(i,j,chimishe(s[i][j],d));
if(e.F.F==i && e.F.S==j){
good[i][j][d]=1;
}else{
out[e.F.F][e.F.S][e.S].pb(mp(mp(i,j),d));
}
}
}
}
}
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
for(ll d=0;d<4;d++){
if(good[i][j][d]){
dfs(i,j,d,getid(i,j));
}
}
}
}
for(ll i=0;i<maxn*maxn;i++)for(ll l=0;l<9;l++)for(ll r=0;r<9;r++)dp[i][l][r]=inf;
for(ll t=1;t<=n;t++){
for(ll l=0;l+t-1<n;l++){
ll r=l+t-1;
vector<pii> vecc;
for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
ll u=getid(i,j);
ll res=inf;
if(t==1 && s[i][j]==l){
res=0;
}
for(ll z=l;z<r;z++){
res=min(res,dp[u][l][z]+dp[u][z+1][r]);
}
if(res!=inf){
vecc.pb(mp(res,u));
}
}
stack<ll> stk,stkk;
sort(vecc.begin(),vecc.end());
reverse(vecc.begin(),vecc.end());
for(ll w=0;vecc.size() || stk.size();w++){
while(vecc.size() && vecc.back().F==w){
stk.push(vecc.back().S);
vecc.pop_back();
}
while(stk.size()){
ll v=stk.top();
stk.pop();
if(dp[v][l][r]>w){
dp[v][l][r]=w;
for(auto e:inp[v]){
if(dp[e][l][r]==inf){
stkk.push(e);
}
}
}
}
swap(stk,stkk);
}
}
}
ll ans=inf;
for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
ans=min(ans,dp[getid(i,j)][0][n-1]);
}
if(ans==inf){
cout<<-1;
}else{
cout<<ans;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
163840 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
