Submission #1109940

#TimeUsernameProblemLanguageResultExecution timeMemory
1109940simona1230Palembang Bridges (APIO15_bridge)C++17
63 / 100
2071 ms7356 KiB
#include <bits/stdc++.h> using namespace std; long long k,n,num,other; pair<long long,long long> p[100001]; bool cmp(pair<long long,long long> p1,pair<long long,long long> p2) { return p1.first+p1.second<p2.first+p2.second; } void read() { cin>>k>>n; for(long long i=1;i<=n;i++) { char c1,c2; long long x,y; cin>>c1>>x>>c2>>y; if(c1==c2)other+=abs(x-y); else { num++; p[num]={min(x,y),max(x,y)}; } } sort(p+1,p+num+1,cmp); if(num==0) { cout<<other<<endl; exit(0); } } void solve1() { vector<long long> v; for(long long i=1;i<=num;i++) { v.push_back(p[i].first); v.push_back(p[i].second); } sort(v.begin(),v.end()); long long x=v[v.size()/2]; long long ans=other+num; for(long long i=0;i<v.size();i++) { ans+=abs(v[i]-x); } cout<<ans<<endl; } void solve2() { long long ans=1e18; if(num==1) { cout<<other+1+p[1].second-p[1].first<<endl; exit(0); } for(long long i=1;i<num;i++) { vector<long long> v1,v2; for(long long j=1;j<=num;j++) { if(j<=i) { v1.push_back(p[j].first); v1.push_back(p[j].second); } else { v2.push_back(p[j].first); v2.push_back(p[j].second); } } sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); long long x1=v1[v1.size()/2]; long long x2=v2[v2.size()/2]; long long curr=0; for(long long j=0;j<v1.size();j++) curr+=abs(v1[j]-x1); for(long long j=0;j<v2.size();j++) curr+=abs(v2[j]-x2); ans=min(ans,curr+other+num); } cout<<ans<<endl; } int main() { read(); if(k==1)solve1(); else solve2(); return 0; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 1 3 A 1 B 1 A 5 B 5 A 6 B 6 */

Compilation message (stderr)

bridge.cpp: In function 'void solve1()':
bridge.cpp:53:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(long long i=0;i<v.size();i++)
      |                       ~^~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:94:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(long long j=0;j<v1.size();j++)
      |                           ~^~~~~~~~~~
bridge.cpp:96:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(long long j=0;j<v2.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...