제출 #60532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60532		Flugan42	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	232 ms	3024 KiB

bridge

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

#define rep(i, from, to) for(int i = from; i < to; i++)
#define inf 1000000000000000000

int main(){
  char a,b; ll n,c,d,k,s = 0,s1 = 0;
  cin >> k >> n;
  vi Q;
  rep(i, 0, n){
    cin >> a >> c >> b >> d;
    if (a == b) s += abs(d-c);
    else { Q.push_back(c); Q.push_back(d); }
  }
  sort(Q.begin(), Q.end());
  //rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
  s += Q.size()/2;
  if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
  else {
    vi d1, d2;
    d1.assign(Q.size(), 0);
    d2.assign(Q.size(), 0);
    d1[0] = 0; d2.back() = 0;
    rep(i, 1, Q.size()){
      d1[i] = d1[i-1]+Q[i]-Q[0];
      d2[Q.size()-i-1] = d2[Q.size()-i]+Q.back()-Q[Q.size()-i-1];
    }
    //rep(i,0,Q.size()) cout << d1[i] << " " << d2[i] << endl;
    s1 = inf;
    rep(i, 0, Q.size()-1){
      ll temp = 0; ll b1 = i/2, b2 = (Q.size()+i)/2;
      temp += d1[i]-d1[b1];
      temp -= (Q[b1]-Q[0])*(i-b1);
      temp += d1.back()-d1[b2];
      temp -= (Q[b2]-Q[0])*(Q.size()-b2-1);

      temp += d2[0]-d2[b1];
      temp -= (Q.back()-Q[b1])*b1;
      temp += d2[i+1]-d2[b2];
      temp -= (Q.back()-Q[b2])*(b2-i-1);
      //cout << i << " " << temp << " " << s1 << endl;
      s1 = min(temp, s1);
    }
  }
  cout << s+s1 << endl;
}

/*
0 1 2 3 4 5 6 7 8 9 10   11 12 13 14 15 16
0 1 2 3 4 5 6 7 8 9   10 11 12 13 14 15 16
*/

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

bridge.cpp: In function 'int main()':
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:28:19:
   if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
                   ~~~~~~~~~~~~~~              
bridge.cpp:28:15: note: in expansion of macro 'rep'
   if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
               ^~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:34:9:
     rep(i, 1, Q.size()){
         ~~~~~~~~~~~~~~                        
bridge.cpp:34:5: note: in expansion of macro 'rep'
     rep(i, 1, Q.size()){
     ^~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:40:9:
     rep(i, 0, Q.size()-1){
         ~~~~~~~~~~~~~~~~                      
bridge.cpp:40:5: note: in expansion of macro 'rep'
     rep(i, 0, Q.size()-1){
     ^~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37