fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define sz 105
  3. #define ll long long
  4. #define INF INT_MAX
  5. using namespace std;
  6.  
  7. //WA on test 12
  8.  
  9. ll n, m, beauty;
  10.  
  11. ll dp[sz][sz][sz];
  12. ll col[sz];
  13. ll cost[sz][sz];
  14.  
  15. int main(){
  16. 	cin>>n>>m>>beauty;
  17.  
  18. 	for(ll i=0; i<sz; i++){
  19. 		for(ll j=0; j<sz; j++) memset(dp[i][j], -1, sizeof(dp[i][j]));
  20. 	}
  21.  
  22.  
  23. 	for(ll i=1; i<=n; i++) cin>>col[i];
  24.  
  25.  
  26. 	for(ll i=1; i<=n; i++){
  27. 		for(ll j=1; j<=m; j++){
  28. 			cin>>cost[i][j];
  29. 		}
  30. 	}
  31.  
  32.  
  33. 	if(col[1]!=0){
  34. 		dp[1][1][col[1]]=0;
  35. 	}
  36. 	else{
  37. 		for(ll i=1; i<=m; i++){
  38. 			dp[1][1][i] = cost[1][i];
  39. 		}
  40. 	}
  41.  
  42.  
  43. 	ll mn, m1, m2;
  44.  
  45. 	for(ll i=2; i<=n; i++){
  46. 		for(ll j=1; j<=beauty; j++){
  47. 			mn = INF;
  48. 			if(col[i]!=0){
  49. 				for(ll k=1; k<=m; k++){
  50. 					if(k==col[i]) continue;
  51. 					if(dp[i-1][j-1][k]!=-1){
  52. 						mn = min(mn, dp[i-1][j-1][k]);
  53. 					}
  54. 				}
  55.  
  56. 				if(mn!=INF) dp[i][j][col[i]] = mn;
  57.  
  58. 				if(dp[i-1][j][col[i]]!=-1){
  59. 					dp[i][j][col[i]] = min(dp[i-1][j][col[i]], mn);
  60. 				}
  61. 			}
  62. 			else{
  63. 				m1=m2=INF;
  64. 				for(ll l=1; l<=m; l++){
  65. 					ll v = dp[i-1][j-1][l];
  66. 					if(v!=-1){
  67. 						if(m1>v){
  68. 							m2=m1;
  69. 							m1=v;
  70. 						}
  71. 						else if(m1==v) m2=v;
  72. 						else if(m2>v) m2=v;
  73. 					}
  74. 				}
  75.  
  76. 				for(ll k=1; k<=m; k++){
  77. 					if(m1!=INF){
  78. 						if(dp[i-1][j-1][k]==m1){
  79. 							mn = m2+cost[i][k];
  80. 						}else mn = m1+cost[i][k];
  81. 					}
  82. 					if(mn!=INF) dp[i][j][k] = mn;
  83.  
  84. 					if(dp[i-1][j][k]!=-1){
  85. 						dp[i][j][k] = min(dp[i-1][j][k]+cost[i][k], mn);
  86. 					}
  87. 				}
  88. 			}
  89. 		}
  90. 	}
  91.  
  92. //	for(ll i=1; i<=n; i++){
  93. //		cout<<"\nFor i="<<i<<endl;
  94. //		for(ll j=1; j<=beauty; j++){
  95. //			cout<<j<<": ";
  96. //			for(ll k=1; k<=m; k++){
  97. //				cout<<dp[i][j][k]<<" ";
  98. //			}cout<<"\n";
  99. //		}
  100. //	}
  101.  
  102. 	mn=INF;
  103. 	if(col[n]!=0) cout<<dp[n][beauty][col[n]];
  104. 	else{
  105. 		for(ll i=1; i<=m; i++){
  106. 			mn = min(dp[n][beauty][i], mn);
  107. 		}
  108. 		if(mn==INF){
  109. 			cout<<-1;
  110. 		}
  111. 		else cout<<mn<<endl;
  112. 	}
  113. }
Success #stdin #stdout 0s 12608KB
comments (?)
stdin
copy 
3 2 2
0 0 0
1 2
3 4
5 6
stdout
copy 
10
https://ideone.com/OW6sYs
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!