fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. int f1(const std::vector<int> &p, int target) {
  6.   int sol = 0, now;
  7.   std::vector<int>::const_iterator i = p.begin();
  8.   std::vector<int>::const_iterator j = p.begin();
  9.   i++; j++;
  10.  
  11.   for (; i != p.end() && *i + *j <= target; ++i)
  12.     if (i != j)
  13.       sol = *i + *j;
  14.  
  15.   if (i > p.begin() + 1)
  16.     --i;
  17.   else
  18.     return 0;
  19.  
  20.   for (;;) {
  21.     // loop-out2
  22.     if (j >= p.end() - 1)
  23.       break;
  24.  
  25.     if (*i + *(j + 1) <= target)
  26.       ++j;
  27.     else
  28.       --i;
  29.     // loop-out1
  30.     if (i == p.begin())
  31.       break;
  32.  
  33.     if (i != j && (now = *i + *j) > sol)
  34.       sol = now;
  35.   }
  36.   return sol;
  37. }
  38.  
  39. int f2(std::vector<int> const &p, int const target) {
  40.   int size = p.size();
  41.   std::vector<std::vector<int> > table;
  42.   std::vector<int>::const_iterator i = p.begin();
  43.   for (;i != p.end(); ++i) {
  44.     std::vector<int> line;
  45.     std::vector<int>::const_iterator j = p.begin();
  46.     for (;j != p.end(); ++j)
  47.       line.push_back(*i + *j);
  48.     table.push_back(line);
  49.   }
  50.   int sol = 0;
  51.   for (int i = 0; i < size; i++)
  52.     for (int j = 0; j < size; j++)
  53.       if (i != j && table[i][j] <= target && table[i][j] > sol)
  54.         sol = table[i][j];
  55.   return sol;
  56. }
  57.  
  58. #if 1
  59. int main() {
  60.   int N, D, t;
  61.   std::vector<int> p, m;
  62.   std::cin >> N >> D;
  63.   if (N <= 1 || D == 0)
  64.     return 0;
  65.   p.reserve(N); m.reserve(D);
  66.   for (int i = 0; i < N; i++) { std::cin >> t; p.push_back(t); }
  67.   p.push_back(0);
  68.   for (int i = 0; i < D; i++) { std::cin >> t; m.push_back(t); }
  69.  
  70.   std::sort(p.begin(), p.end());
  71.  
  72.   std::vector<int>::const_iterator mIterator;
  73.   for (mIterator = m.begin(); mIterator != m.end(); mIterator++)
  74.     std::cout << f1(p, *mIterator) << std::endl;
  75.   return 0;
  76. }
  77.  
  78. #else
  79.  
  80. #include <cstdlib>
  81. #define N 10000
  82. #define LIM 100000
  83. int main() {
  84.   std::vector<int> p;
  85.   for (int seed = 0; seed < N; seed++) {
  86.     ::srand(seed);
  87.     int n = ::rand() % 20;
  88.     int d = ::rand() % (LIM * 2);
  89.     if (n <= 1)
  90.       continue;
  91.  
  92.     std::cout << seed;
  93.     for (int i = 0; i < n; i++)
  94.       p.push_back(::rand() % LIM);
  95.     std::sort(p.begin(), p.end());
  96.  
  97.     int b = f2(p, d);
  98.  
  99.     p.push_back(0);
  100.     std::sort(p.begin(), p.end());
  101.     int a = f1(p, d);
  102.  
  103.     if (a != b)
  104.       std::cout << ":NG." << std::endl;
  105.     else
  106.       std::cout << ":OK." << std::endl;
  107.     p.clear();
  108.   }
  109.   return 0;
  110. }
  111.  
  112. #endif
  113. /* end */
  114.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
5 2
4000
3000
1000
2000
5000
10000
3000
stdout
copy 
9000
3000
https://ideone.com/yY7y4b
language:
C++ (gcc 8.3)
created:
11 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!