fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Numeric Constants
  5. #define N 1000000007
  6. #define maxs 200005
  7. #define mins 2005
  8. #define eps 1e-14
  9. #define imax 2000000200
  10. #define llmax 1000000002000000000ll
  11. #define pi 3.141592653589793
  12.  
  13. // Others
  14. #define ll long long
  15. #define pb push_back
  16. #define gc getchar_unlocked
  17. #define iosbase ios_base::sync_with_stdio(false)
  18. #define pii pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define ppi pair<pair<int,int>,int>
  21. #define ppl pair<pii,ll>
  22. #define vi vector<int>
  23. #define sc scanf
  24. #define pr printf
  25. #define lld I64d
  26. #define F first
  27. #define S second
  28. #define siter set<int>::iterator
  29. #define p_pq priority_queue
  30. #define ub upper_bound
  31. #define lb lower_bound
  32. #define mps make_pair
  33.  
  34. class comp{
  35. public:
  36. 	bool operator()(ppl p1,ppl p2){
  37. 		return p2.S<p1.S;
  38. 	}
  39. };
  40. priority_queue<ppl,vector<ppl>,comp>pq;
  41. ll dist[mins][mins];
  42. int cols[mins],mark[mins][mins];
  43. ll weights[mins];
  44.  
  45. int main()
  46. {
  47. 	int n,i,j,k,m,s,t;
  48. 	sc("%d",&n);
  49. 	sc("%d %d",&k,&m);
  50. 	for(i=1;i<=n;i++){
  51. 		sc("%lld",&weights[i]);
  52. 	}
  53. 	for(i=1;i<=n;i++){
  54. 		sc("%d",&cols[i]);
  55. 		cols[i]--;
  56. 	}
  57. 	sc("%d %d",&s,&t);
  58. 	for(i=1;i<=n;i++){
  59. 		for(j=0;j<(1<<10);j++){
  60. 			dist[i][j]=llmax;
  61. 		}
  62. 	}
  63. 	dist[s][1<<cols[s]]=0;
  64. 	pq.push(mps(mps(s,1<<cols[s]),0));
  65. 	while(!pq.empty()){
  66. 		ppl p1=pq.top();
  67. 		pq.pop();
  68. 		if(mark[p1.F.F][p1.F.S]){
  69. 			continue;
  70. 		}
  71. 		mark[p1.F.F][p1.F.S]=1;
  72. 		for(i=-k;i<=k;i++){
  73. 			if((p1.F.F+i)<=0 || (p1.F.F+i)>n){
  74. 				continue;
  75. 			}
  76. 			ppl p2=p1;
  77. 			p2.S+=abs(weights[p1.F.F]-weights[p1.F.F+i]);
  78. 			p2.F.S=(p2.F.S|(1<<cols[p1.F.F+i]));
  79. 			p2.F.F=p1.F.F+i;
  80. 			if(dist[p2.F.F][p2.F.S]>p2.S){
  81. 				dist[p2.F.F][p2.F.S]=p2.S;
  82. 				pq.push(p2);
  83. 			}
  84. 		}
  85. 	}
  86. 	ll ans=llmax;
  87. 	for(i=0;i<(1<<10);i++){
  88. 		if(__builtin_popcount(i)<=m){
  89. 			ans=min(ans,dist[t][i]);
  90. 		}
  91. 	}
  92. 	if(ans==llmax){
  93. 		pr("-1\n");
  94. 	}
  95. 	else{
  96. 		pr("%lld\n",ans);
  97. 	}
  98.  
  99. 	return 0;
  100. }
Time limit exceeded #stdin #stdout 5s 50608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B47vs0
language:
C++14 (gcc 8.3)
created:
7 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!