oj.uz

Submission #45817

# Submission time Handle Problem Language Result Execution time Memory
45817 2018-04-16T08:10:33 Z Talant Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 5696 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
#define int long long

using namespace std;

const int  inf = (int)1e15 + 7;
const int N = (int)2e5 + 7;

int k,n;
int x,y;
int suma,sumb;
int pos,pos1;
int ca,cb;
int ans = inf,cur;

char ch,ch1;

vector <int> a,b,vec;
vector <pair<int,int> > vc;

int f (int x,int y) {
      suma = 0;
      for (int i = 0; i < (int)vc.size(); i ++)
            suma += min((abs(vc[i].fr - x) + abs(vc[i].sc - x)),(abs(vc[i].fr - y) + abs(vc[i].sc - y)));

      return (suma + cur + (int)a.size());
}

 main () {
      cin >> k >> n;

      for (int i = 1; i <= n; i ++) {
            cin >> ch >> x >> ch1 >> y;
            if (ch == ch1) {
                  cur += abs(x - y);
            }
            else {
                  if (ch == 'A') a.pb(x),b.pb(y);
                  else b.pb(x),a.pb(y);
                  vec.pb(x);
                  vec.pb(y);
                  vc.pb({x,y});
            }
      }
      vec.pb(0);
      vec.pb(1e9);
      sort (vec.begin(),vec.end());
      vec.erase(unique(vec.begin(),vec.end()),vec.end());

      sort (a.begin(),a.end());
      sort (b.begin(),b.end());

      if (k == 1) {
            for (int i = 0; i < (int)a.size(); i ++)
                  suma += abs(a[i] - vec[0]),sumb += abs(b[i] - vec[0]);

            for (int j = 0; j < (int)vec.size(); j ++) {
                  ans = min(ans,cur + suma + sumb + (int)a.size());

                  pos = upper_bound(a.begin(),a.end(),vec[j]) - a.begin();
                  suma -= (((int)a.size() - pos) * 1ll * (vec[j + 1] - vec[j]));
                  suma += (pos * 1ll * (vec[j + 1] - vec[j]));

                  pos = upper_bound(b.begin(),b.end(),vec[j]) - b.begin();
                  sumb -= (((int)b.size() - pos) * 1ll * (vec[j + 1] - vec[j]));
                  sumb += (pos * 1ll * (vec[j + 1] - vec[j]));
            }
            cout << ans << endl;
      }
      else {
            for (int i = 0; i < vec.size(); i ++) {
                  for (int j = 0; j < vec.size(); j ++) {
                        if (i != j) {
                              ans = min(ans,f(vec[i],vec[j]));
                        }
                  }
            }
            cout << ans << endl;
      }
}
/**
Sample 1
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Sample 2
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

1 3
A 0 B 0
A 1 B 1
A 1000000000 B 1000000000
**/

Compilation message

bridge.cpp:35:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main () {
        ^
bridge.cpp: In function 'int main()':
bridge.cpp:77:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < vec.size(); i ++) {
                             ~~^~~~~~~~~~~~
bridge.cpp:78:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for (int j = 0; j < vec.size(); j ++) {
                                   ~~^~~~~~~~~~~~

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 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 4 ms 408 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 3 ms 520 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 5 ms 560 KB Output is correct
9 Correct 5 ms 560 KB Output is correct
10 Correct 4 ms 560 KB Output is correct
11 Correct 4 ms 560 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 5 ms 748 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 85 ms 5368 KB Output is correct
13 Correct 234 ms 5488 KB Output is correct
14 Correct 154 ms 5488 KB Output is correct
15 Correct 105 ms 5488 KB Output is correct
16 Correct 113 ms 5488 KB Output is correct
17 Correct 157 ms 5628 KB Output is correct
18 Correct 195 ms 5628 KB Output is correct
19 Correct 220 ms 5628 KB Output is correct
20 Correct 117 ms 5696 KB Output is correct
21 Correct 201 ms 5696 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5696 KB Output is correct
2 Correct 2 ms 5696 KB Output is correct
3 Correct 2 ms 5696 KB Output is correct
4 Correct 14 ms 5696 KB Output is correct
5 Correct 7 ms 5696 KB Output is correct
6 Correct 2 ms 5696 KB Output is correct
7 Correct 2 ms 5696 KB Output is correct
8 Correct 18 ms 5696 KB Output is correct
9 Correct 18 ms 5696 KB Output is correct
10 Correct 17 ms 5696 KB Output is correct
11 Correct 2 ms 5696 KB Output is correct
12 Correct 18 ms 5696 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5696 KB Output is correct
2 Correct 2 ms 5696 KB Output is correct
3 Correct 2 ms 5696 KB Output is correct
4 Correct 15 ms 5696 KB Output is correct
5 Correct 5 ms 5696 KB Output is correct
6 Correct 2 ms 5696 KB Output is correct
7 Correct 2 ms 5696 KB Output is correct
8 Correct 21 ms 5696 KB Output is correct
9 Correct 18 ms 5696 KB Output is correct
10 Correct 20 ms 5696 KB Output is correct
11 Correct 3 ms 5696 KB Output is correct
12 Correct 18 ms 5696 KB Output is correct
13 Correct 3 ms 5696 KB Output is correct
14 Correct 42 ms 5696 KB Output is correct
15 Execution timed out 2047 ms 5696 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5696 KB Output is correct
2 Correct 2 ms 5696 KB Output is correct
3 Correct 2 ms 5696 KB Output is correct
4 Correct 19 ms 5696 KB Output is correct
5 Correct 5 ms 5696 KB Output is correct
6 Correct 2 ms 5696 KB Output is correct
7 Correct 2 ms 5696 KB Output is correct
8 Correct 18 ms 5696 KB Output is correct
9 Correct 20 ms 5696 KB Output is correct
10 Correct 21 ms 5696 KB Output is correct
11 Correct 2 ms 5696 KB Output is correct
12 Correct 18 ms 5696 KB Output is correct
13 Correct 3 ms 5696 KB Output is correct
14 Correct 46 ms 5696 KB Output is correct
15 Execution timed out 2072 ms 5696 KB Time limit exceeded
16 Halted 0 ms 0 KB -