Submission #660018

#TimeUsernameProblemLanguageResultExecution timeMemory
660018aebovPalembang Bridges (APIO15_bridge)C++17
22 / 100
36 ms1548 KiB
#include<iostream> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<utility> #include<unordered_map> #include<vector> #include<set> #define pii pair<int,int> #define pll pair<ll, ll> #define F first #define S second #define ll long long #define pb push_back using namespace std; const int N = (int)1e5 + 5, mod = (ll)1e9 + 7; int n, k, x, y; char ch, hc; ll sm = 0, sm2 = (ll)1e18 + 18; void sub(){ exit(0); // cerr << "\n entered #sub 2 \n"; vector<int> cv; vector<pii> vc; vc.pb({0,0}); for(int i = 1; i <= n; i ++){ cin >> ch >> x >> hc >> y; if(x < y)swap(x, y); if(ch == hc) sm += x - y; else vc.pb({y, x}); } n = vc.size() - 1; // cout << "N " << n << endl; for(int i = 1; i <= n; i ++) { cv.pb(vc[i].F); cv.pb(vc[i].S); } sort(cv.begin(), cv.end()); // for(auto u : cv)cout << u << endl; for(int i = 0; i < cv.size(); i ++){ for(int j = i; j < cv.size(); j ++) { int x = cv[i], y = cv[j]; ll sum = 0; for(int z = 1; z <= n; z ++){ if(vc[z].S < x) sum += (x<<1) - vc[z].F - vc[z].S + 1; else if(vc[z].F > y) sum += vc[z].F + vc[z].S - (y<<1) + 1; else if(x < vc[z].F && vc[z].S < y)sum += min(vc[z].F + vc[z].S -(x<<1) + 1,(y<<1) - vc[z].F - vc[z].S + 1); else sum += vc[z].S - vc[z].F + 1; } sm2 = min(sm2, sum); } } // cout << sm << " " << sm2 << endl; cout << sm + sm2 << endl; exit(0); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> k >> n; vector<int> vc; //if(k == 2 && n < 101)sub(); // cerr << "\n enteres #sub1 \n"; for(int i = 1; i <= n; i ++){ cin >> ch >> x >> hc >> y; if(ch == hc) sm += abs(x - y); else sm ++, vc.pb(x), vc.pb(y); } sort(vc.begin(), vc.end()); int pos = vc[(vc.size() - 1) / 2]; for(auto x : vc)sm += abs(x - pos); cout << sm << endl; }

Compilation message (stderr)

bridge.cpp: In function 'void sub()':
bridge.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < cv.size(); i ++){
      |                 ~~^~~~~~~~~~~
bridge.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j = i; j < cv.size(); j ++) {
      |                  ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...