Submission #45876

#	Time	Username	Problem	Language	Result	Execution time	Memory
45876		mirbek01	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	171 ms	7136 KiB

bridge

# include <bits/stdc++.h>

# define f first
# define s second

using namespace std;

const int N = 1e5 + 2;

int n, k, cn;
long long ans = 1e18, p1[N], s1[N], p2[N], s2[N], ss;
vector <int> v, v1, v2;
pair < pair <int, int> , pair <char, char> > a[N];

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

      for(int i = 1; i <= n; i ++){
            cin >> a[i].s.f >> a[i].f.f >> a[i].s.s >> a[i].f.s;
            if(a[i].s.f != a[i].s.s) {
                  cn ++;
                  v1.push_back(a[i].f.f), v2.push_back(a[i].f.s);
            } else {
                  ss += abs(a[i].f.s - a[i].f.f);
            }
            v.push_back(a[i].f.f);
            v.push_back(a[i].f.s);
      }

      v1.push_back(-1e9);
      v2.push_back(-1e9);

      sort(a + 1, a + n + 1);
      sort(v.begin(), v.end());
      sort(v1.begin(), v1.end());
      sort(v2.begin(), v2.end());

      for(int i = 1; i <= cn; i ++){
            p1[i] = p1[i - 1] + v1[i];
            p2[i] = p2[i - 1] + v2[i];
      }
      for(int i = cn; i >= 1; i --){
            s1[i] = s1[i + 1] + v1[i];
            s2[i] = s2[i + 1] + v2[i];
      }

      int pos = 0, ps = 0;

      for(int i = 0; i < v.size(); i ++){
            long long res = 0;
            int x = v[i];
            while(pos + 1 <= cn && v1[pos + 1] <= x) pos ++;
            while(ps + 1 <= cn && v2[ps + 1] <= x) ps ++;
            res += x * 1ll * pos - p1[pos];
            res += x * 1ll * ps - p2[ps];
            res += s1[pos + 1] - x * 1ll * (cn - pos);
            res += s2[ps + 1] - x * 1ll * (cn - ps);
            ans = min(ans, res + cn + ss);
      }
      if(k == 2){
            for(int i = 0; i < v.size(); i ++){
                  for(int j = i + 1; j < v.size(); j ++){
                        long long res = 0;
                        for(int k = 1; k <= n; k ++){
                              if(a[k].s.f == a[k].s.s){
                                    res += abs(a[k].f.f - a[k].f.s);
                              } else {
                                    int x = (v[i] + v[j] + 1) >> 1;
                                    int f = a[k].f.f + a[k].f.s >> 1;
                                    if(f <= x)
                                          res += abs(a[k].f.f - v[i]) + abs(a[k].f.s - v[i]) + 1;
                                    else
                                          res += abs(a[k].f.f - v[j]) + abs(a[k].f.s - v[j]) + 1;
                              }
                        }
                        ans = min(ans, res);
                  }
            }
      }

      cout << ans << endl;
}
/***
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
***/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < v.size(); i ++){
                      ~~^~~~~~~~~~
bridge.cpp:61:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i ++){
                            ~~^~~~~~~~~~
bridge.cpp:62:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = i + 1; j < v.size(); j ++){
                                      ~~^~~~~~~~~~
bridge.cpp:69:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                                     int f = a[k].f.f + a[k].f.s >> 1;
                                                      ^

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