제출 #894536

#제출 시각아이디문제언어결과실행 시간메모리
894536salmonPalembang Bridges (APIO15_bridge)C++14
100 / 100
487 ms23892 KiB
#include <bits/stdc++.h> using namespace std; int N; int K; char c,c1; vector<pair<long long int,pair<int,int>>> v; long long int h,h1; long long int sum = 0; long long int ans = 0; long long int big = 1e18; long long int lst[100100]; int main(){ scanf(" %d",&K); scanf(" %d",&N); set<pair<int,int>> s; map<int,int> mep; for(int i = 0; i < N; i++){ scanf(" %c",&c); scanf(" %lld",&h); scanf(" %c",&c1); scanf(" %lld",&h1); if(c == c1){ ans += abs(h - h1); } else{ v.push_back(make_pair(h + h1, make_pair(h,h1))); } } sort(v.begin(),v.end()); auto it = s.begin(); lst[0] = 0; for(int i = 0; i < v.size(); i++){ if(i == 0){ sum = abs(v[i].second.second - v[i].second.first); s.insert(make_pair(v[i].second.second, mep[v[i].second.second])); mep[v[i].second.second]++; s.insert(make_pair(v[i].second.first, mep[v[i].second.first])); mep[v[i].second.first]++; it = s.begin(); } else{ int flag = 0; pair<int,int> ii = make_pair(v[i].second.first, mep[v[i].second.first] ); mep[v[i].second.first]++; pair<int,int> ii1 = make_pair(v[i].second.second, mep[v[i].second.second]); mep[v[i].second.second]++; flag += (*it) < ii; flag += (*it) < ii1; int lum = 0; if(flag == 0){ s.insert(ii); s.insert(ii1); lum += it -> first; advance(it,-1); lum -= it -> first; sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); sum += abs(lum)* 2; } if(flag == 1){ s.insert(ii); s.insert(ii1); sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); } if(flag == 2){ s.insert(ii); s.insert(ii1); advance(it,1); sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); } } lst[i + 1] = sum; } s.clear(); mep.clear(); big = sum; for(int i = v.size() - 1; i >= 0; i--){ if(i == v.size() - 1){ sum = abs(v[i].second.second - v[i].second.first); s.insert(make_pair(v[i].second.second, mep[v[i].second.second])); mep[v[i].second.second]++; s.insert(make_pair(v[i].second.first, mep[v[i].second.first])); mep[v[i].second.first]++; it = s.begin(); } else{ int flag = 0; pair<int,int> ii = make_pair(v[i].second.first, mep[v[i].second.first] ); mep[v[i].second.first]++; pair<int,int> ii1 = make_pair(v[i].second.second, mep[v[i].second.second]); mep[v[i].second.second]++; flag += (*it) < ii; flag += (*it) < ii1; int lum = 0; if(flag == 0){ s.insert(ii); s.insert(ii1); lum += it -> first; advance(it,-1); lum -= it -> first; sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); sum += abs(lum) * 2; } if(flag == 1){ s.insert(ii); s.insert(ii1); sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); } if(flag == 2){ s.insert(ii); s.insert(ii1); advance(it,1); sum += abs(it -> first - ii.first); sum += abs(it -> first - ii1.first); } } big = min(big, lst[i] + sum); } if(K == 2) printf("%lld",big + v.size() + ans); else printf("%lld", lst[v.size()] + ans + v.size()); } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */

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

bridge.cpp: In function 'int main()':
bridge.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
bridge.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(i == v.size() - 1){
      |            ~~^~~~~~~~~~~~~~~
bridge.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
bridge.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
bridge.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
bridge.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf(" %lld",&h);
      |         ~~~~~^~~~~~~~~~~~
bridge.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf(" %c",&c1);
      |         ~~~~~^~~~~~~~~~~
bridge.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf(" %lld",&h1);
      |         ~~~~~^~~~~~~~~~~~~
#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...