Submission #1009779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009779		asdfgrace	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	30 ms	4860 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*
build 1 or 2 bridges
add to baseline of sum of all distances driven without crossing bridge + n
then only consider people crossing

k=1:
minimize the sum of all abs(s[i] - x) + abs(t[i] - x)
one of the given locs is optimal
so here treat all s[i] and t[i] the same, sort, etc.

k=2:
if l <= x or y <= r, dist = r - l
else, dist = r - l + 2 * (dist btwn either end & closest bridge)
assume x < y
5 cases
1) left of x
2) contains x
3) btwn x, y
4) contains y
5) right of y
best y for each x?
everything to left/containing x is handled (i.e. everything with l <= x)
n^2 sol:
for (each i)
case 1: x = l[i]
everything true
case 2: x = r[i]

*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int k, n;
  cin >> k >> n;
  vector<array<int, 2>> a;
  long long bsl = 0;
  for (int i = 0; i < n; i++) {
    char c1, c2; int i1, i2;
    cin >> c1 >> i1 >> c2 >> i2;
    if (c1 == c2) {
      bsl += abs(i2 - i1);
    } else {
      if (i2 < i1) swap(i1, i2);
      a.push_back({i1, i2});
      bsl++;
    }
  }
  n = (int) a.size();
  vector<int> b;
  for (int i = 0; i < n; i++) {
    b.push_back(a[i][0]); b.push_back(a[i][1]);
  }
  sort(b.begin(), b.end());
  if (k == 1) {
    long long sum = 0;
    for (int i = 0; i < 2 * n; i++) {
      sum += b[i] - b[0];
    }
    long long best = sum;
    for (int i = 1; i < 2 * n; i++) {
      sum += (long long) i * (b[i] - b[i - 1]);
      sum -= (long long) (2 * n - i) * (b[i] - b[i - 1]);
      best = min(best, sum);
    }
    cout << best + bsl << '\n'; 
  } else {
    long long best = 1e18;
    for (int x = 0; x < 2 * n; x++) {
      for (int y = x; y < 2 * n; y++) {
        long long sum = 0;
        for (int i = 0; i < n; i++) {
          sum += min(abs(a[i][0] - b[x]) + abs(a[i][1] - b[x]),
            abs(a[i][0] - b[y]) + abs(a[i][1] - b[y]));
        }
        best = min(best, sum);
      }
    }
    cout << best + bsl << '\n';
  }
}

/*
any observations help

check every line
IF YOUR LINES AREN'T WRONG
CHECK IF YOUR LINES ARE IN THE RIGHT ORDER

NEVER GIVE UP
*/

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37