Submission #100428

#	Time	Username	Problem	Language	Result	Execution time	Memory
100428		cvele	Cipele (COCI18_cipele)	C++14	27 / 90	126 ms	3856 KiB

cipele

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9