oj.uz

Submission #115667

# Submission time Handle Problem Language Result Execution time Memory
115667 2019-06-08T14:22:41 Z ckodser Robots (APIO13_robots) C++14
60 / 100
 535 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=510;
const ll inf=1e9+800;

const ll di[4]={-1,0 ,+1,0 };
const ll dj[4]={0 ,+1,0 ,-1};
const ll maxm=5e5+500;

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);
	}
}


vector<ll> stk[maxm];

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;
			ll sz=0;
			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++){//////////////////////////// 120*n*m
					res=min(res,dp[u][l][z]+dp[u][z+1][r]);
				}
				if(res!=inf){
					stk[res].pb(u);
					sz++;
				}
			}
			for(ll w=0;sz!=0;w++){
				while(stk[w].size()){
					ll v=stk[w].back();
					stk[w].pop_back();
					sz--;
					if(dp[v][l][r]>w){
						dp[v][l][r]=w;
						for(auto e:inp[v]){
							if(dp[e][l][r]==inf){
								stk[w+1].pb(e);
								sz++;
							}
						}
					}
				}
			}
		}
	}
	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;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 144596 KB Output is correct
2 Correct 116 ms 144504 KB Output is correct
3 Correct 115 ms 144484 KB Output is correct
4 Correct 115 ms 144592 KB Output is correct
5 Correct 119 ms 144504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 144596 KB Output is correct
2 Correct 116 ms 144504 KB Output is correct
3 Correct 115 ms 144484 KB Output is correct
4 Correct 115 ms 144592 KB Output is correct
5 Correct 119 ms 144504 KB Output is correct
6 Correct 112 ms 144380 KB Output is correct
7 Correct 115 ms 144612 KB Output is correct
8 Correct 117 ms 144504 KB Output is correct
9 Correct 129 ms 144524 KB Output is correct
10 Correct 118 ms 144508 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 144596 KB Output is correct
2 Correct 116 ms 144504 KB Output is correct
3 Correct 115 ms 144484 KB Output is correct
4 Correct 115 ms 144592 KB Output is correct
5 Correct 119 ms 144504 KB Output is correct
6 Correct 112 ms 144380 KB Output is correct
7 Correct 115 ms 144612 KB Output is correct
8 Correct 117 ms 144504 KB Output is correct
9 Correct 129 ms 144524 KB Output is correct
10 Correct 118 ms 144508 KB Output is correct
11 Correct 386 ms 152736 KB Output is correct
12 Correct 159 ms 149764 KB Output is correct
13 Correct 317 ms 149408 KB Output is correct
14 Correct 535 ms 154384 KB Output is correct
15 Correct 322 ms 150388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 144596 KB Output is correct
2 Correct 116 ms 144504 KB Output is correct
3 Correct 115 ms 144484 KB Output is correct
4 Correct 115 ms 144592 KB Output is correct
5 Correct 119 ms 144504 KB Output is correct
6 Correct 112 ms 144380 KB Output is correct
7 Correct 115 ms 144612 KB Output is correct
8 Correct 117 ms 144504 KB Output is correct
9 Correct 129 ms 144524 KB Output is correct
10 Correct 118 ms 144508 KB Output is correct
11 Correct 386 ms 152736 KB Output is correct
12 Correct 159 ms 149764 KB Output is correct
13 Correct 317 ms 149408 KB Output is correct
14 Correct 535 ms 154384 KB Output is correct
15 Correct 322 ms 150388 KB Output is correct
16 Runtime error 396 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -