제출 #78350

#제출 시각아이디문제언어결과실행 시간메모리
78350shoemakerjo전선 연결 (IOI17_wiring)C++14
13 / 100
52 ms19004 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define prev previousguy #define ll long long #define maxn 100010 #define pii pair<int, int> ll dp[2][maxn]; int prev, cur; int n, m; const ll inf = 1LL << 62; vector<pii> stuff; ll suf[maxn]; ll pref[maxn]; ll min_total_length(vector<int> r, vector<int> b) { n = r.size(); m = b.size(); cur = 0; prev = 1; for (int i = 0; i < n; i++) { stuff.push_back(pii(r[i], 0)); } for (int i = 0; i < m; i++) { stuff.push_back(pii(b[i], 1)); } sort(stuff.begin(), stuff.end()); int lastsize = -1; for (int i = 0; i < n+m; i++) { int cstart = i; int cend = i; while (cend < n + m && stuff[cend+1].second == stuff[cend].second) ++cend; // cout << "group from " << cstart << " " << cend << endl; swap(prev, cur); int csize = cend - cstart+1; if (lastsize == -1) { dp[cur][0] = 0; for (int j = 1; j <= csize; j++) dp[cur][j] = inf; } else { ll gap = stuff[cstart].first - stuff[cstart-1].first; // cout << "GAP: " << gap << endl; int ostart = cstart - lastsize; int oend = cstart-1; //do suffix for how many we take suf[0] = 0; for (int j = 1; j <= lastsize; j++) { suf[j] = suf[j-1] + stuff[oend].first - stuff[oend-j+1].first; } pref[0] = 0; //prefix for how many we take for (int j = 1; j <= csize; j++) { pref[j] = pref[j-1] + stuff[cstart+j-1].first - stuff[cstart].first; } for (int j = 0; j <= csize; j++) { dp[cur][j] = inf; } //do minimum from the left ll curmin = inf; for (int j = 0; j <= csize; j++) { //consider taking less than me from the left if (lastsize - j >= 0) curmin = min(curmin, dp[prev][lastsize-j] + suf[j]); dp[cur][j] = min(dp[cur][j], curmin + pref[j] + gap*j); // cout << " " << j << ": " << pref[j] << // " " << dp[cur][j] << " - " << curmin << // " suf: " << suf[j] << endl; } curmin = inf; for (int j = lastsize; j > csize; j--) { //consider taking all but this many curmin = min(curmin, j * gap + dp[prev][lastsize-j] + suf[j]); } for (int j = csize; j >= 0; --j) { if (lastsize - j >= 0) curmin = min(curmin, j * gap + dp[prev][lastsize-j] + suf[j]); dp[cur][j] = min(dp[cur][j], curmin + pref[j]); } } // cout << cstart << " to " << cend << endl; // for (int j = 0; j <= csize; j++) { // cout << " " << j << " : " << dp[cur][j] << endl; // } // cout << endl; lastsize = csize; i = cend; } return dp[cur][lastsize]; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:54:8: warning: unused variable 'ostart' [-Wunused-variable]
    int ostart = cstart - lastsize;
        ^~~~~~
#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...