Submission #45752

#	Time	Username	Problem	Language	Result	Execution time	Memory
45752		mirbek01	Palembang Bridges (APIO15_bridge)	C++17	17 / 100	2068 ms	2500 KiB

bridge

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, k, s[N], f[N];
long long ans = 1e18;
char a[N], b[N];
vector <int> v;

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

      for(int i = 1; i <= n; i ++){
            cin >> a[i] >> s[i] >> b[i] >> f[i];
            v.push_back(s[i]);
            v.push_back(f[i]);
      }
      for(int i = 0; i < v.size(); i ++){
            long long res = 0;
            int x = v[i];
            for(int j = 1; j <= n; j ++){
                  if(a[j] == b[j]){
                        res += abs(s[j] - f[j]);
                  } else {
                        res += abs(s[j] - x) + abs(x - f[j]) + 1;
                  }
            }
            ans = min(ans, res);
      }
      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] == b[k]){
                                    res += abs(s[k] - f[k]);
                              } else {
                                    res += min( abs(s[k] - v[i]) + abs(f[k] - v[i]) + 1, abs(s[k] - v[j]) + abs(f[k] - 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:20:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < v.size(); i ++){
                      ~~^~~~~~~~~~
bridge.cpp:33:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i ++){
                            ~~^~~~~~~~~~
bridge.cpp:34:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = i + 1; j < v.size(); j ++){
                                      ~~^~~~~~~~~~

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