oj.uz

Submission #41493

# Submission time Handle Problem Language Result Execution time Memory
41493 2018-02-17T09:49:22 Z Nurlykhan Palembang Bridges (APIO15_bridge) C++14
8 / 100
 2000 ms 5844 KB 
    #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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 5 ms 424 KB Output is correct
4 Correct 12 ms 588 KB Output is correct
5 Correct 12 ms 612 KB Output is correct
6 Correct 5 ms 612 KB Output is correct
7 Correct 5 ms 612 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 11 ms 612 KB Output is correct
10 Correct 6 ms 612 KB Output is correct
11 Correct 5 ms 612 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 13 ms 672 KB Output is correct
5 Correct 12 ms 672 KB Output is correct
6 Correct 4 ms 672 KB Output is correct
7 Correct 5 ms 672 KB Output is correct
8 Correct 5 ms 672 KB Output is correct
9 Correct 10 ms 672 KB Output is correct
10 Correct 6 ms 672 KB Output is correct
11 Correct 6 ms 672 KB Output is correct
12 Execution timed out 2025 ms 5844 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 2 ms 5844 KB Output is correct
3 Incorrect 2 ms 5844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 2 ms 5844 KB Output is correct
3 Incorrect 2 ms 5844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 1 ms 5844 KB Output is correct
3 Incorrect 2 ms 5844 KB Output isn't correct
4 Halted 0 ms 0 KB -