oj.uz

Submission #137846

# Submission time Handle Problem Language Result Execution time Memory
137846 2019-07-28T11:04:27 Z triplem5ds Palembang Bridges (APIO15_bridge) C++14
8 / 100
 2000 ms 5764 KB 
///Let the game start
#pragma GCC optimize("Ofast,no-stack-protector")
#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define pb push_back
using ll = long long;
using ii = pair<int, int>;
using db = long double;
using ull = unsigned long long;
const int N = 3e5 + 5, MOD = 998244353;
const db EPS = 1e-7;
int A[N], B[N];
int main(){
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(0); cin.tie(0);
#endif // ONLINE_JUDGE
 
  int n, k;
  cin >> n >> k;  swap(k,n);
 
  ll ans = 0;
  char c1, c2;
  std::vector<ii> vp;
  for(int i = 0; i < n; i++){
    cin >> c1 >> A[i] >> c2 >> B[i];
    if(c1 == c2){
      ans += abs(A[i] - B[i]);
    } else {
      if(A[i] > B[i])swap(A[i], B[i]);
      vp.push_back(ii(A[i], B[i]));
    }
  }
 
  sort(vp.begin(), vp.end());
  n = vp.size();
  ans += n;
 
  if(k == 1){
 
    std::vector<int> cities;
 
    for(auto x : vp){
      cities.pb(x.F);
      cities.pb(x.S);
    }
 
    sort(cities.begin(), cities.end());
    cities.resize(unique(cities.begin(), cities.end()) - cities.begin());
    long long out = LLONG_MAX;
    if(vp.empty())out = 0;
    for(auto x : cities){
        long long val = 0;
        for(auto v : vp){
          if(v.second <= x){
            val += 2 * x - (v.first + v.second);
          } else if(v.first <= x){
            val += v.S - v.F;
          } else {
            val += (v.F + v.S) - 2 * x;
          }
        }
        out = min(out, val);
    }
    cout << ans + out << '\n';
 
  }
 
 
  return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 7 ms 376 KB Output is correct
12 Correct 97 ms 4204 KB Output is correct
13 Execution timed out 2029 ms 5764 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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