제출 #431993

#제출 시각아이디문제언어결과실행 시간메모리
431993rumen_m전선 연결 (IOI17_wiring)C++17
0 / 100
5 ms3532 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e18; const int maxn = 2e5+5; pair <int,bool> v[maxn]; long long dp[maxn]; long long pref[maxn],suff[maxn]; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n = r.size(); int m = b.size(); int i,j; for(i=0;i<n;i++) { v[i] = {r[i],0}; } for(i=0;i<m;i++) { v[i+n] = {b[i],1}; } for(i=0;i<=n+m;i++) dp[i] = inf; sort(v,v+m+n); int start = 0; while(v[start].second==v[0].second)start++; for(i=start; i< n+m; i++) { //cout<<i<<endl; start = i; int l = start-1; while(v[l].second==v[start-1].second)l--; l++; int r = start; while(v[r].second==v[start].second)r++; r--; pref[start-1] = 0; for(i=start-2;i>=l;i--) pref[i] = pref[i+1] + (v[start-1].first - v[i].first); suff[start] = 0; for(i=start+1;i<=r;i++) suff[i] = suff[i-1] + (v[i].first - v[start].first); long long mini = inf; for(i = start; i <= r; i++) { int pos = start - (i-start+1); if(pos>=l) { mini = min(mini,min(dp[pos],dp[pos-1]) + pref[pos]); } dp[i] = min (dp[i], mini + (long long)(i-start+1)*(v[start].first-v[start-1].first)+ suff[i]); } i = r; } return dp[n+m-1]; }

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

wiring.cpp:4:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    4 | const int inf = 1e18;
      |                 ^~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:8: warning: unused variable 'j' [-Wunused-variable]
   12 |  int i,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...