oj.uz

Submission #1009750

# Submission time Handle Problem Language Result Execution time Memory
1009750 2024-06-28T02:55:54 Z asdfgrace Palembang Bridges (APIO15_bridge) C++17
22 / 100
 34 ms 3028 KB 
#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 + 1; 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 14 ms 3028 KB Output is correct
13 Correct 34 ms 2512 KB Output is correct
14 Correct 21 ms 2516 KB Output is correct
15 Correct 15 ms 1496 KB Output is correct
16 Correct 16 ms 2776 KB Output is correct
17 Correct 18 ms 2600 KB Output is correct
18 Correct 21 ms 2772 KB Output is correct
19 Correct 26 ms 2608 KB Output is correct
20 Correct 19 ms 2748 KB Output is correct
21 Correct 22 ms 2772 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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