제출 #297645

#제출 시각아이디문제언어결과실행 시간메모리
297645AaronNaiduPalembang Bridges (APIO15_bridge)C++14
22 / 100
54 ms6388 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll k, n; ll s, t, numLeft, numRight, distFrom0; ll minSum; char p, q; vector<pair<ll, ll> > events, eventss; ll solveProblem() { // cout << "Solving problem:\n"; sort(events.begin(), events.end()); ll prevLocation = 0; ll finAns = 1000000000000000; if (events.size() == 0) { finAns = minSum; } // cout << "Entering for loop\n"; for (int i = 0; i < events.size(); i++) { ll currLocation = events[i].first; distFrom0 -= numRight * (currLocation - prevLocation); distFrom0 += numLeft * (currLocation - prevLocation); if (events[i].second == -1) { numRight--; } else { numLeft++; } finAns = min(finAns, minSum + 2 * distFrom0); //cout << "At location " << currLocation << " dist is " << distFrom0 << '\n'; prevLocation = currLocation; } //cout << "Solved problem\n"; return finAns; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> k >> n; minSum = 0; numLeft = numRight = distFrom0 = 0; if (k == 1) { for (int i = 0; i < n; i++) { cin >> p >> s >> q >> t; if (p == q) { minSum += abs(t - s); } else { minSum += 1 + abs(t - s); ll b = max(t, s); ll a = min(t, s); events.push_back({a, -1}); events.push_back({b, 1}); numRight++; distFrom0 += a; } } //cout << "Min sum is " << minSum << "\n"; //cout << "Initial dist: " << distFrom0 << "\n"; sort(events.begin(), events.end()); ll prevLocation = 0; ll finAns = 1000000000000000; if (events.size() == 0) { finAns = minSum; } for (int i = 0; i < events.size(); i++) { ll currLocation = events[i].first; distFrom0 -= numRight * (currLocation - prevLocation); distFrom0 += numLeft * (currLocation - prevLocation); if (events[i].second == -1) { numRight--; } else { numLeft++; } finAns = min(finAns, minSum + 2 * distFrom0); //cout << "At location " << currLocation << " dist is " << distFrom0 << '\n'; prevLocation = currLocation; } cout << finAns << "\n"; return 0; } for (int i = 0; i < n; i++) { //cout << "This i = " << i << "\n"; cin >> p >> s >> q >> t; if (p == q) { minSum += abs(t - s); } else { minSum += 1 + abs(t - s); ll b = max(t, s); ll a = min(t, s); eventss.push_back({a, b}); } } //cout << "Checking size\n"; if(eventss.size() < 2) { cout << minSum << "\n"; return 0; } ll finAns = 1000000000000000; //cout << "Eventss size: " << eventss.size() << "\n"; for (int i = 0; i < eventss.size(); i++) { // cout << "i = " << i << "\n"; distFrom0 = numLeft = numRight = 0; events.clear(); for (int j = 0; j < eventss.size(); j++) { // cout << "j1 = " << j << "\n"; if (eventss[j].second < eventss[i].first or eventss[j].first > eventss[i].first) { //cout << "In if\n"; events.push_back({eventss[j].first, -1}); events.push_back({eventss[j].second, 1}); distFrom0 += eventss[j].first; numRight++; } } finAns = min(finAns, solveProblem()); distFrom0 = numLeft = numRight = 0; events.clear(); for (int j = 0; j < eventss.size(); j++) { if (eventss[j].second < eventss[i].second or eventss[j].first > eventss[i].second) { events.push_back({eventss[j].first, -1}); events.push_back({eventss[j].second, 1}); distFrom0 += eventss[j].first; numRight++; } } finAns = min(finAns, solveProblem()); } cout << finAns << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'll solveProblem()':
bridge.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < events.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < events.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
bridge.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < eventss.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
bridge.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int j = 0; j < eventss.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~
bridge.cpp:142:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for (int j = 0; j < eventss.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...