oj.uz

Submission #100428

# Submission time Handle Problem Language Result Execution time Memory
100428 2019-03-11T09:19:03 Z cvele Cipele (COCI18_cipele) C++14
27 / 90
 126 ms 3856 KB 
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 100005;

int n, m;
long long pref[N];
vector <int> a, b;

long long ss(int x, int y) {
  return (pref[y] - (x > 0 ? pref[x - 1] : 0));
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    b.push_back(x);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  if (b.size() < a.size()) {
    swap(a, b);
    swap(n, m);
  }
  long long sum = 0;
  for (int i = 0; i < a.size(); i++) sum += a[i];
  pref[0] = b[0];
  for (int i = 1; i < m; i++) {
    pref[i] = pref[i - 1] + b[i];
  }
  long long ans = 2e18;
  int w;
  for (int i = n - 1; i < m; i++) {
    if (abs(sum - ss(i - n + 1, i)) < ans) {
      ans = abs(sum - ss(i - n + 1, i));
      w = i;
    }
  }
  ans = -2e9;
  int ce = 0;
  for (int i = w - n + 1; i <= w; i++) {
    ans = max((int) ans, abs(a[ce++] - b[i]));
  }
  cout << ans << endl;
  return 0;
}

Compilation message

cipele.cpp: In function 'int main()':
cipele.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) sum += a[i];
                   ~~^~~~~~~~~~
cipele.cpp:56:7: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int w;
       ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3568 KB Output is correct
2 Correct 105 ms 3856 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 3744 KB Output is correct
2 Correct 126 ms 3780 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 10 ms 512 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 3228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 3440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 3216 KB Output isn't correct
2 Halted 0 ms 0 KB -