Submission #1054741

#TimeUsernameProblemLanguageResultExecution timeMemory
1054741RojusPalembang Bridges (APIO15_bridge)C++14
22 / 100
26 ms4472 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int k, n; cin >> k >> n; vector<pair<int, int>> v; vector<int> sarasas; vector<pair<int, int>> vidurio_taskai; set<int> s; long long priedas=0; for(int i=0; i<n; i++) { char cg, cd; int ig, id; cin >> cg >> ig >> cd >> id; if(cg!=cd) { priedas++; v.push_back({ig, id}); vidurio_taskai.push_back({(ig+id)/2, v.size()-1}); sarasas.push_back(ig); sarasas.push_back(id); } else { priedas+=abs(ig-id); } } if(k==1) { sort(sarasas.begin(), sarasas.end()); int tiltas=sarasas.size()/2; long long sum=priedas; for(int i=0; i<v.size(); i++) { sum+=abs(v[i].first-sarasas[tiltas])+abs(v[i].second-sarasas[tiltas]); } cout << sum; } else { sort(sarasas.begin(), sarasas.end()); sort(vidurio_taskai.begin(), vidurio_taskai.end()); priority_queue<int> dideli, mazi; long long suma_dideliu=0, suma_mazu=0; long long ats[vidurio_taskai.size()-1]; for(int i=0; i<vidurio_taskai.size()-1; i++) { //cout << "Paimta " << i+1 << " poru: "; int x=v[vidurio_taskai[i].second].first; int y=v[vidurio_taskai[i].second].second; if(x<y) swap(x, y); if(dideli.size()==0) { dideli.push(-x); mazi.push(y); suma_dideliu+=x; suma_mazu+=y; } else { if(y>-dideli.top()) { suma_dideliu-=-dideli.top(); suma_mazu+=-dideli.top(); mazi.push(-dideli.top()); dideli.pop(); suma_dideliu+=x+y; dideli.push(-x); dideli.push(-y); } ///prielaida, kad abu i maziausius niekada neis else { suma_dideliu+=x; suma_mazu+=y; dideli.push(-x); mazi.push(y); } } //int mediana=-dideli.top(); ats[i]=suma_dideliu-suma_mazu; //cout << ats[i][0] << endl; } ///----------------------------------------- while(!mazi.empty()) mazi.pop(); while(!dideli.empty()) dideli.pop(); suma_dideliu=0, suma_mazu=0; for(int i=vidurio_taskai.size()-1; i>0; i--) { //cout << "Paimta " << vidurio_taskai.size()-i << " poru nuo galo: "; int x=v[vidurio_taskai[i].second].first; int y=v[vidurio_taskai[i].second].second; if(x<y) swap(x, y); //cout << x << ' ' << y << " "; if(dideli.size()==0) { dideli.push(-x); mazi.push(y); suma_dideliu+=x; suma_mazu+=y; } else { if(x>-dideli.top() || x>mazi.top()) { suma_dideliu+=x; suma_mazu+=y; dideli.push(-x); mazi.push(y); } ///prielaida, kad abu i didziausius niekada neis else { suma_mazu-=mazi.top(); suma_dideliu+=mazi.top(); dideli.push(-mazi.top()); mazi.pop(); suma_mazu+=x+y; mazi.push(x); mazi.push(y); } } //int mediana=-dideli.top(); ats[i-1]+=suma_dideliu-suma_mazu; //cout << ats[i-1][1] << endl; } long long atsakymas=LONG_MAX; for(int i=0; i<v.size()-1; i++) { atsakymas=min(atsakymas, ats[i]); } atsakymas+=priedas; cout << atsakymas; } return 0; } /* 2 5 A 1 B 6 A 2 B 1 B 7 A 7 B 6 A 1 B 5 A 5 */

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0; i<v.size(); i++)
      |                      ~^~~~~~~~~
bridge.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0; i<vidurio_taskai.size()-1; i++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int i=0; i<v.size()-1; i++)
      |                      ~^~~~~~~~~~~
#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...