oj.uz

Submission #60542

# Submission time Handle Problem Language Result Execution time Memory
60542 2018-07-24T10:14:52 Z Flugan42 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 174 ms 2836 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

#define rep(i, from, to) for(int i = from; i < to; i++)
#define inf 1000000000000000000
#define sz(x) (ll)(x).size()

int main(){
  char a,b; ll n,c,d,k,s = 0,s1 = 0;
  cin >> k >> n;
  vi Q;
  rep(i, 0, n){
    cin >> a >> c >> b >> d;
    if (a == b) s += abs(d-c);
    else { Q.push_back(c); Q.push_back(d); }
  }
  sort(Q.begin(), Q.end());
  s += sz(Q)/2;
  if (sz(Q) == 0) { cout << s << endl; exit(0); }
  if (k == 1) rep(i, 0, sz(Q)) s += abs(Q[i]-Q[sz(Q)/2]);
  else {
    vi d1, d2;
    d1.assign(sz(Q), 0);
    d2.assign(sz(Q), 0);
    d1[0] = 0; d2.back() = 0;
    rep(i, 1, sz(Q)){
      d1[i] = d1[i-1]+Q[i]-Q[0];
      d2[sz(Q)-i-1] = d2[sz(Q)-i]+Q.back()-Q[sz(Q)-i-1];
    }
    s1 = inf;
    rep(i, 0, sz(Q)-1){
      ll temp = 0; ll b1 = i/2, b2 = (sz(Q)+i)/2;
      temp += d1[i]-d1[b1];
      temp -= (Q[b1]-Q[0])*(i-b1);
      temp += d1.back()-d1[b2];
      temp -= (Q[b2]-Q[0])*(sz(Q)-b2-1);

      temp += d2[0]-d2[b1];
      temp -= (Q.back()-Q[b1])*b1;
      temp += d2[i+1]-d2[b2];
      temp -= (Q.back()-Q[b2])*(b2-i-1);
      s1 = min(temp, s1);
    }
  }
  cout << s+s1 << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 4 ms 536 KB Output is correct
5 Correct 5 ms 536 KB Output is correct
6 Correct 4 ms 536 KB Output is correct
7 Correct 4 ms 540 KB Output is correct
8 Correct 5 ms 544 KB Output is correct
9 Correct 5 ms 544 KB Output is correct
10 Correct 5 ms 544 KB Output is correct
11 Correct 4 ms 544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 4 ms 544 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 5 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 4 ms 728 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 4 ms 728 KB Output is correct
9 Correct 4 ms 728 KB Output is correct
10 Correct 4 ms 728 KB Output is correct
11 Correct 5 ms 728 KB Output is correct
12 Correct 69 ms 2780 KB Output is correct
13 Correct 153 ms 2780 KB Output is correct
14 Correct 104 ms 2780 KB Output is correct
15 Correct 112 ms 2780 KB Output is correct
16 Correct 124 ms 2780 KB Output is correct
17 Correct 135 ms 2780 KB Output is correct
18 Correct 140 ms 2780 KB Output is correct
19 Correct 174 ms 2780 KB Output is correct
20 Correct 117 ms 2836 KB Output is correct
21 Correct 135 ms 2836 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2836 KB Output is correct
2 Correct 3 ms 2836 KB Output is correct
3 Incorrect 3 ms 2836 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 2836 KB Output is correct
2 Correct 2 ms 2836 KB Output is correct
3 Incorrect 3 ms 2836 KB Output isn't correct
4 Halted 0 ms 0 KB -