fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <utility>
  5.  
  6. using namespace std;
  7.  
  8. struct wear{
  9.     int a,b,c;
  10. };
  11.  
  12. vector<vector<int> > memovul;
  13. int n;
  14.  
  15. int vest(const int* tmp,const wear* wd,const int d);
  16.  
  17. int main()
  18. {
  19. 	int d;
  20. 	cin>>d>>n;
  21. 	//table.resize(n,vector<int>(n,-1));
  22. 	memovul.resize(d);
  23. 	for(int i=0;i<d;i++){
  24. 		memovul[i].resize(n,-1);
  25. 	}
  26. 	int* temperature=new int[d];
  27. 	wear* wearsdata=new wear[n];
  28. 	for(int i=d-1;i>=0;i--){
  29. 		cin>>temperature[i];
  30. 	}
  31. 	for(int i=0;i<n;i++){
  32. 		cin>>wearsdata[i].a>>wearsdata[i].b>>wearsdata[i].c;
  33. 	}
  34. 	cout<<vest(temperature,wearsdata,d)<<endl;
  35. }
  36. int vest(const int* tmp,const wear* wd,const int d)
  37. {
  38. 	pair<int,int> table[2][2]={pair<int,int>(-1,0),pair<int,int>(-1,0),pair<int,int>(-1,0),pair<int,int>(-1,0)};
  39. 	int dabs;
  40. 	for(int i=0;i<d;i++){
  41. 		table[i%2][0].first=-1;
  42. 		for(int j=0;j<n;j++){
  43. 			if(wd[j].a<=tmp[i] && wd[j].b>=tmp[i]){
  44. 				if(table[i%2][0].first==-1){
  45. 					table[i%2][0].first=j;
  46. 					table[i%2][1].first=j;
  47. 					if(i){
  48. 						dabs=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
  49. 						table[i%2][0].second=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
  50. 						if(dabs>table[i%2][0].second){
  51. 							table[i%2][0].second=dabs;
  52. 						}
  53. 						table[i%2][1].second=table[i%2][0].second;
  54. 					}
  55. 				}else{
  56. 					if(wd[table[i%2][0].first].c<wd[j].c){
  57. 						if(i){
  58. 							dabs=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
  59. 							table[i%2][0].second=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
  60. 							if(dabs>table[i%2][0].second){
  61. 								table[i%2][0].second=dabs;
  62. 							}
  63. 						}
  64. 						table[i%2][0].first=j;
  65. 					}else if(wd[table[i%2][1].first].c>wd[j].c){
  66. 						if(i){
  67. 							dabs=abs(wd[table[(i+1)%2][1].first].c-wd[j].c)+table[(i+1)%2][1].second;
  68. 							table[i%2][1].second=abs(wd[table[(i+1)%2][0].first].c-wd[j].c)+table[(i+1)%2][0].second;
  69. 							if(dabs>table[i%2][1].second){
  70. 								table[i%2][1].second=dabs;
  71. 							}
  72. 						}
  73. 						table[i%2][1].first=j;
  74. 					}
  75. 				}
  76. 			}
  77. 		}
  78. 	}
  79. 	if(table[(d+1)%2][0].second<table[(d+1)%2][1].second){
  80. 		return table[(d+1)%2][1].second;
  81. 	}
  82. 	return table[(d-1)%2][0].second;
  83. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6 6
41
22
17
54
55
1
18 59 19
1 32 75
14 40 97
12 32 82
14 14 0
31 52 42
stdout
copy 
235
https://ideone.com/OUUxgH
language:
C++14 (gcc 8.3)
created:
9 days 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!