Submission #997415

#TimeUsernameProblemLanguageResultExecution timeMemory
997415doducanhPalembang Bridges (APIO15_bridge)C++14
22 / 100
130 ms11312 KiB
#include<bits/stdc++.h> using namespace std; #define ii pair<int,int> #define fi first #define se second int k,n; long long sumL=0,sumU=0; vector<ii>v; multiset<int>low; multiset<int>up; long long pref[100005]; bool cmp(ii a,ii b) { return (a.fi+a.se)<(b.fi+b.se); } void capnhat(int x) { int val; if(low.size()==0)val=1000000007; else val=*low.rbegin(); if(x<=val){ low.insert(x); sumL+=x; } else{ up.insert(x); sumU+=x; } if(low.size()>up.size()+1){ up.insert(*low.rbegin()); sumU+=(*low.rbegin()); sumL-=(*low.rbegin()); low.erase(low.find(*low.rbegin())); } else if(up.size()>low.size()){ low.insert(*up.begin()); sumL+=(*up.begin()); sumU-=(*up.begin()); up.erase(up.find(*up.begin())); } } main() { cin>>k>>n; long long delt=0; for(int i=1;i<=n;i++){ char a,b; int x,y; cin>>a>>x>>b>>y; if(a==b){ delt+=abs(x-y); } else{ v.push_back({x,y}); } } sort(v.begin(),v.end(),cmp); long long ans=LLONG_MAX; for(int i=0;i<v.size();i++){ capnhat(v[i].fi); capnhat(v[i].se); pref[i]=sumU-sumL; } ans=min(ans,sumU-sumL+(long long)v.size()); if(k==2){ sumL=0,sumU=0; for(int x:low)low.erase(low.find(x)); for(int x:up)up.erase(up.find(x)); for(int i=v.size()-1;i>0;i--){ capnhat(v[i].fi); capnhat(v[i].se); ans=min(ans,pref[i-1]+sumU-sumL+(long long)v.size()); } } cout<<ans+delt; return 0; }

Compilation message (stderr)

bridge.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<v.size();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...