Submission #41493

#	Time	Username	Problem	Language	Result	Execution time	Memory
41493		Nurlykhan	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2025 ms	5844 KiB

bridge

    #include <bits/stdc++.h>
     
    #define pii pair<int, int>
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define ld long double
    #define sz(v) int(v.size())
    #define all(v) v.begin(), v.end()
    #define vec vector<int>
    #define dead not_bad
    #define bad gooood
     
    #define left not_right
    #define y1 what
     
    using namespace std;
     
    const int N = (int) 2e5 + 10;
    const int M = (int) 2e6;
    const ll LINF = (ll) 2e18;
    const int INF = (int) 1e9 + 7;
    const int ALPHA = 26;
    const int mod = INF;
    const double PI = 3.14159265359;
    const ld EPS = (ld) 1e-12;
     
    const int nx[4] = {0, 0, -1, 1};
    const int ny[4] = {1, -1, 0, 0};
     
      vector<ll> x_arr;
     
    ll solve(vector<ll> a, vector<ll> b) {
      for (auto it : a) {
        x_arr.pb(it);
      }
      for (auto it : b) {
        x_arr.pb(it);
      }
      int n = sz(a);
      ll ans = LINF;
      for (auto x : x_arr) {
        ll cur = 0;
        for (int i = 0; i < n; i++) {
          if (a[i] <= x && x <= b[i]) {
            cur += b[i] - a[i];
          } else if (a[i] > x) {
            cur += a[i] + b[i] - 2 * x;
          } else if (b[i] < x) {
            cur += 2 * x - (a[i] + b[i]);
          } else {
            assert(0);
          }
        }
        ans = min(ans, cur);
      }
      return ans + n;
    }
     
     
    int k, n;
     
    int main() {
      #define fn "teams"
      #ifdef witch
          freopen("input.txt", "r", stdin);
          freopen("output.txt", "w", stdout);
      #else
          //freopen(fn".in", "r", stdin);
          //freopen(fn".out", "w", stdout);
      #endif  
      int nn;
      ll ans = 0;
      cin >> k >> nn;
      vector<ll> A, B;
      for (int i = 1; i <= nn; i++) {
        char ta, tb;
        ll x1, x2;
        cin >> ta >> x1 >> tb >> x2;
        //cout << ta << ' ' << x1 << ' ' << tb << ' ' << x2 << endl;
        if (x1 > x2) 
          swap(x1, x2);
        if (ta == tb) {
          x_arr.pb(x1); x_arr.pb(x2);
          ans += x2 - x1;
        } else {
          A.pb(x1);
          B.pb(x2);
        }
      }
      cout << ans + solve(A, B);
      return 0;
    }

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