제출 #132540

#제출 시각아이디문제언어결과실행 시간메모리
132540rondojim전선 연결 (IOI17_wiring)C++17
30 / 100
190 ms12636 KiB
/// In The Name Of God #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, l, r) for (int i = (l); i >= (r); i--) #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = (int)4e5 + 7; const int inf = (int)1e9 + 7; const int mod = (int)1e9 + 7; const ll linf = (ll)1e18 + 7; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}; const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; using namespace std; int sz; pair <ll, int> t[N]; ll dp[N], s[N]; int nxt[N]; ll get(int l, int r) { if (nxt[l] == -1) assert(0); int n, m; int id = nxt[l] - 1; n = id - l + 1; m = r - id; ll res = 0; res += t[id].f * (id - l + 1) - (s[id] - s[l - 1]); res += (s[r] - s[id]) - t[id + 1].f * (r - id); res += max(n, m) * (t[id + 1].f - t[id].f); return res; } ll min_total_length(vector <int> _r, vector <int> _b) { for (auto it : _r) t[++sz] = {it, 0}; for (auto it : _b) t[++sz] = {it, 1}; sort (t + 1, t + 1 + sz); rep(i, 1, sz) s[i] = s[i - 1] + t[i].f; { /// calc next int pos[2] = {-1, -1}; per(i, sz, 1) { int b = t[i].s; nxt[i] = pos[b ^ 1]; pos[b] = i; } } memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; int cnt = 0, last = -1; int pos[2] = {-1, -1}; int R = -1; rep(i, 1, sz) { if (t[i].s != last) { cnt = 1, last = t[i].s; R = nxt[i]; if (nxt[R] == -1) R = sz; else R = nxt[R] - 1; } else ++cnt; if (pos[t[i].s ^ 1] != -1) { /// go to the left int j = pos[t[i].s ^ 1]; ll sum = s[i] - s[j]; dp[i] = min(dp[i], dp[i - 1] + t[i].f - t[j].f); dp[i] = min(dp[i], dp[j - 1] + sum - (ll)t[j].f * (i - j)); } { /// go to the right int id = -1; int cur = 0; if (nxt[i] == -1) continue; while (R - nxt[i] + 1 > nxt[i] - i) R--; //cerr << i << ' ' << nxt[i] << ' ' << R << nl; rep(j, max(nxt[i], R - 100), R) { dp[j] = min(dp[j], min(dp[i - 1], dp[i]) + get(i, j)); if (id == -1) id = j; ++cur; //if (cur > id - i) break; } } pos[t[i].s] = i; } return dp[sz]; } #ifdef IOI2018 namespace read { void read() { int n, m; assert(2 == scanf("%d %d", &n, &m)); vector<int> r(n), b(m); for(int i = 0; i < n; i++) assert(1 == scanf("%d", &r[i])); for(int i = 0; i < m; i++) assert(1 == scanf("%d", &b[i])); long long res = min_total_length(r, b); printf("%lld\n", res); ioi } } int main() { #ifdef IOI2018 freopen ("in.txt", "r", stdin); freopen ("slow.out", "w", stdout); #endif read :: read(); ioi } #endif //// 000 111 111111111
#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...