oj.uz

Submission #115670

# Submission time Handle Problem Language Result Execution time Memory
115670 2019-06-08T14:31:00 Z ckodser Robots (APIO13_robots) C++14
60 / 100
 604 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};

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 132728 KB Output is correct
2 Correct 110 ms 132728 KB Output is correct
3 Correct 111 ms 132728 KB Output is correct
4 Correct 109 ms 132744 KB Output is correct
5 Correct 144 ms 132736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 132728 KB Output is correct
2 Correct 110 ms 132728 KB Output is correct
3 Correct 111 ms 132728 KB Output is correct
4 Correct 109 ms 132744 KB Output is correct
5 Correct 144 ms 132736 KB Output is correct
6 Correct 107 ms 132664 KB Output is correct
7 Correct 111 ms 132732 KB Output is correct
8 Correct 107 ms 132824 KB Output is correct
9 Correct 109 ms 132728 KB Output is correct
10 Correct 112 ms 132704 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 132728 KB Output is correct
2 Correct 110 ms 132728 KB Output is correct
3 Correct 111 ms 132728 KB Output is correct
4 Correct 109 ms 132744 KB Output is correct
5 Correct 144 ms 132736 KB Output is correct
6 Correct 107 ms 132664 KB Output is correct
7 Correct 111 ms 132732 KB Output is correct
8 Correct 107 ms 132824 KB Output is correct
9 Correct 109 ms 132728 KB Output is correct
10 Correct 112 ms 132704 KB Output is correct
11 Correct 391 ms 138080 KB Output is correct
12 Correct 133 ms 137424 KB Output is correct
13 Correct 214 ms 137720 KB Output is correct
14 Correct 604 ms 138676 KB Output is correct
15 Correct 299 ms 137772 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 132728 KB Output is correct
2 Correct 110 ms 132728 KB Output is correct
3 Correct 111 ms 132728 KB Output is correct
4 Correct 109 ms 132744 KB Output is correct
5 Correct 144 ms 132736 KB Output is correct
6 Correct 107 ms 132664 KB Output is correct
7 Correct 111 ms 132732 KB Output is correct
8 Correct 107 ms 132824 KB Output is correct
9 Correct 109 ms 132728 KB Output is correct
10 Correct 112 ms 132704 KB Output is correct
11 Correct 391 ms 138080 KB Output is correct
12 Correct 133 ms 137424 KB Output is correct
13 Correct 214 ms 137720 KB Output is correct
14 Correct 604 ms 138676 KB Output is correct
15 Correct 299 ms 137772 KB Output is correct
16 Runtime error 383 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -