oj.uz

Submission #115668

# Submission time Handle Problem Language Result Execution time Memory
115668 2019-06-08T14:25:34 Z ckodser Robots (APIO13_robots) C++14
60 / 100
 703 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;
			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){
					stk[res].pb(u);
					vecc.pb(mp(res,u));
					sz++;
				}
			}
			sort(vecc.begin(),vecc.end());

			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 122 ms 144504 KB Output is correct
2 Correct 116 ms 144620 KB Output is correct
3 Correct 116 ms 144504 KB Output is correct
4 Correct 116 ms 144440 KB Output is correct
5 Correct 117 ms 144632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 144504 KB Output is correct
2 Correct 116 ms 144620 KB Output is correct
3 Correct 116 ms 144504 KB Output is correct
4 Correct 116 ms 144440 KB Output is correct
5 Correct 117 ms 144632 KB Output is correct
6 Correct 116 ms 144452 KB Output is correct
7 Correct 132 ms 144504 KB Output is correct
8 Correct 121 ms 144504 KB Output is correct
9 Correct 117 ms 144464 KB Output is correct
10 Correct 121 ms 144512 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 144504 KB Output is correct
2 Correct 116 ms 144620 KB Output is correct
3 Correct 116 ms 144504 KB Output is correct
4 Correct 116 ms 144440 KB Output is correct
5 Correct 117 ms 144632 KB Output is correct
6 Correct 116 ms 144452 KB Output is correct
7 Correct 132 ms 144504 KB Output is correct
8 Correct 121 ms 144504 KB Output is correct
9 Correct 117 ms 144464 KB Output is correct
10 Correct 121 ms 144512 KB Output is correct
11 Correct 415 ms 153116 KB Output is correct
12 Correct 148 ms 149672 KB Output is correct
13 Correct 229 ms 149616 KB Output is correct
14 Correct 703 ms 155096 KB Output is correct
15 Correct 324 ms 150584 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 144504 KB Output is correct
2 Correct 116 ms 144620 KB Output is correct
3 Correct 116 ms 144504 KB Output is correct
4 Correct 116 ms 144440 KB Output is correct
5 Correct 117 ms 144632 KB Output is correct
6 Correct 116 ms 144452 KB Output is correct
7 Correct 132 ms 144504 KB Output is correct
8 Correct 121 ms 144504 KB Output is correct
9 Correct 117 ms 144464 KB Output is correct
10 Correct 121 ms 144512 KB Output is correct
11 Correct 415 ms 153116 KB Output is correct
12 Correct 148 ms 149672 KB Output is correct
13 Correct 229 ms 149616 KB Output is correct
14 Correct 703 ms 155096 KB Output is correct
15 Correct 324 ms 150584 KB Output is correct
16 Runtime error 407 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -