fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6. int getAns(vector<int>& d1, vector<int>& d2, set<int>& s) {
  7.  
  8. 	vector<int> dist1;
  9. 	vector<int> dist2;
  10.  
  11. 	for(int i = 0; i < d1.size(); ++i) {
  12. 		if(s.find(i) == s.end()) continue;
  13. 		dist1.push_back(d1[i]);
  14. 		dist2.push_back(d2[i]);
  15. 	}
  16.  
  17. 	vector<int> prefix(dist1.size(),0);
  18. 	prefix[0] = dist2[0];
  19. 	for(int i = 1; i < prefix.size(); ++i) {
  20. 		prefix[i] = min(prefix[i-1], dist2[i]);
  21. 	}
  22.  
  23.  
  24. 	vector<int> suffix(dist1.size(),0);
  25. 	suffix[dist1.size()-1] = dist2[dist2.size()-1];
  26. 	for(int i = suffix.size()-2; i >= 0; --i) {
  27. 		suffix[i] = min(suffix[i+1], dist2[i]);
  28. 	}
  29.  
  30. 	int ans =0;
  31.  
  32. 	for(int i = 0; i < dist1.size()-1; ++i) {
  33. 		int suf = i < dist1.size()-1 ? suffix[i+1] : dist1.size() * dist1.size();
  34. 		ans = max(ans, dist1[i] + suf);
  35. 	}
  36.  
  37. 	return min(ans + 1, d1[d1.size()-1]);
  38. }
  39.  
  40. int main() {
  41. 	// your code goes here
  42. 	vector<int> dist1 = {0,1,2,2,3};
  43. 	vector<int> dist2 = {3,2,1,2,0};
  44.  
  45. 	set<int> s = {0,1,3};
  46.  
  47. 	cout << endl << getAns(dist1, dist2,s) << endl;
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/d5PMxN
language:
C++ (gcc 8.3)
created:
4 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!