SRM580 Div1 Easy

250

区間の両端だけを気にすればいい。

view plainprint?

1. class EelAndRabbit {  
2. public:  
3.   int getmax(vector <int> l, vector <int> t)  
4.   {  
5.     const int N = l.size();  
6.     vector<double> T;  
7.     int mx = 1;  
8.     for (int i = 0; i < N; ++i) {  
9.       for (int j = i + 1; j < N; ++j) {  
10.         vector<double> cand;  
11.   
12.         cand.push_back(t[i]);  
13.         cand.push_back(t[i] + l[i]);  
14.   
15.         cand.push_back(t[j]);  
16.         cand.push_back(t[j] + l[j]);  
17.   
18.         for (int a = 0; a < cand.size(); ++a) {  
19.           for (int b = 0; b < cand.size(); ++b) {  
20.             set<int> vis;  
21.             for (int k = 0; k < N; ++k) {  
22.               if (t[k] + l[k] >= cand[a] && cand[a] >= t[k]) {  
23.                 vis.insert(k);  
24.               }  
25.               if (t[k] + l[k] >= cand[b] && cand[b] >= t[k]) {  
26.                 vis.insert(k);  
27.               }  
28.             }  
29.             mx = max(mx, (int)vis.size());  
30.           }  
31.         }  
32.       }  
33.     }  
34.     return mx;  
35.   }  

class EelAndRabbit {
public:
  int getmax(vector <int> l, vector <int> t)
  {
    const int N = l.size();
    vector<double> T;
    int mx = 1;
    for (int i = 0; i < N; ++i) {
      for (int j = i + 1; j < N; ++j) {
        vector<double> cand;

        cand.push_back(t[i]);
        cand.push_back(t[i] + l[i]);

        cand.push_back(t[j]);
        cand.push_back(t[j] + l[j]);

        for (int a = 0; a < cand.size(); ++a) {
          for (int b = 0; b < cand.size(); ++b) {
            set<int> vis;
            for (int k = 0; k < N; ++k) {
              if (t[k] + l[k] >= cand[a] && cand[a] >= t[k]) {
                vis.insert(k);
              }
              if (t[k] + l[k] >= cand[b] && cand[b] >= t[k]) {
                vis.insert(k);
              }
            }
            mx = max(mx, (int)vis.size());
          }
        }
      }
    }
    return mx;
  }