제출 #1196294

#제출 시각아이디문제언어결과실행 시간메모리
1196294LGQ_A3K25Cultivation (JOI17_cultivation)C++20
80 / 100
2093 ms3012 KiB
#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b / __gcd(a,b) #define I first #define II second #define pb push_back #define ii pair<int,int> const int INF = 2e9; const int N = 1e3 + 1; const int MOD = 1e9 + 7; int n, m, k; ll ans = 1e18; namespace sub1 { int a[41][41], b[41][41]; int main() { vector<ii> s; for (int i = 0; i < k; i++) { int u, v; cin >> u >> v; s.pb({u, v}); a[u][v] = 1; } int ans = INF; for (int x = 0; x <= 40; x++) for (int y = 0; y <= 40; y++) if (x + y <= ans) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) b[i][j] = a[i][j]; for (auto [u, v] : s) { int ox = 1, oy = 1; for (int i = 1; i <= max(x, y) && (ox | oy); i++) { if (ox && i <= x) { if (u - i == 0 || b[u - i][v] == 1) ox = 0; else b[u - i][v] = 1; // if (x == 4 && y == 5) cout << u - i << ' ' << v << '\n'; } if (oy && i <= y) { if (u + i == n + 1 || b[u + i][v] == 1) oy = 0; else b[u + i][v] = 1; } } } // if (x == 4 && y == 5) // { // for (int i = 1; i <= n; i++) // for (int j = 1; j <= m; j++) cout << (b[i][j]) << (j == m ? '\n' : ' '); // } int l = 0, r = 0, mid = 0, ok = 1; for (int i = 1; i <= n; i++) { int last = 0, nxt = m + 1, ok1 = 0; for (int j = 1; j <= m; j++) { if (b[i][j]) { ok1 = 1; if (!last) l = max(l, j - 1); else mid = max(mid, j - last - 1); last = j; } int jj = m - j + 1; if (b[i][jj]) { if (nxt == m + 1) r = max(r, nxt - jj - 1); else mid = max(mid, nxt - jj - 1); nxt = jj; } } if (!ok1) { ok = 0; break; } } if (ok) { mid = max(0, mid - l - r); ans = min(ans, x + y + l + r + mid); } // if (ans == 8) cout << x << ' ' << y << '\n'; } cout << ans; return 0; } } namespace sub2 { int a[41][41]; bool cmp(ii x, ii y) { if (x.II < y.II) return true; else if (x.II == y.II) return x.I < y.I; return false; } int main() { vector<ii> s; for (int i = 1; i <= k; i++) { int u, v; cin >> u >> v; s.pb({u, v}); } sort(s.begin(), s.end(), cmp); int ans = INF; for (int tt = 0; tt < k; tt++) { int x = s[tt].I - 1; vector<int> t; for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) t.pb(max(0, s[j].I - x - s[i].I - 1)); t.pb(n - s[i].I); } sort(t.begin(), t.end()); t.resize(unique(t.begin(), t.end()) - t.begin()); for (auto y : t) { // if (x == 0 && y == 4) cout << "fwefwef" << '\n'; if (x + y > ans) break; // cout << x << ' ' << y << '\n'; int cur = x + y; vector<array<int, 3> > p; vector<array<int, 2> > b; for (auto [u, v] : s) { int l = max(1, u - x), r = min(n, u + y); b.pb({l, r}); p.pb({v, l, r}); } sort(b.begin(), b.end()); if (b[0][0] != 1) continue; int R = b[0][1], ok = 1; for (int i = 1; i < k; i++) { if (b[i][0] > R + 1) { ok = 0; break; } else R = b[i][1]; } if (!ok || R != n) continue; int l = 0, r = 0, mid = 0; for (int i = 0; i < k; i++) { int u = p[i][1], v = p[i][2]; for (int j = 0; j < i && (u <= v); j++) { int c = p[j][1], d = p[j][2]; if (c <= u && d >= u) { mid = max(mid, p[j][0] - p[i][0] - 1); u = d + 1; } else if (c <= v && d >= v) { mid = max(mid, p[j][0] - p[i][0] - 1); v = c - 1; } } if (u <= v) l = max(l, p[i][0] - 1); } for (int i = k - 1; i >= 0; i--) { int u = p[i][1], v = p[i][2]; for (int j = i + 1; j < k && (u <= v); j++) { int c = p[j][1], d = p[j][2]; if (c <= u && d >= u) { mid = max(mid, p[j][0] - p[i][0] - 1); u = d + 1; } else if (c <= v && d >= v) { mid = max(mid, p[j][0] - p[i][0] - 1); v = c - 1; } } // if (mid == 2 && !x && y == 4) cout << i << '\n'; if (u <= v) r = max(r, m - p[i][0]); } cur += l + r + max(0, mid - l - r); // if (x == 0 && y == 4) cout << l << ' ' << r << ' ' << mid << '\n'; ans = min(ans, cur); } } cout << ans << '\n'; return 0; } } namespace sub3 { int tg[N], num[N]; ll ans = 1e18; ii p[N]; array<int, 3> cur[N], f[N][N]; // L, R, M struct DQ { deque<ii> q; void add(ii x) { while (q.size() && q.back().I <= x.I) q.pop_back(); q.pb(x); } void del(int x) { while (q.size() && q.front().II <= x) q.pop_front(); } int get() { if (q.empty()) return INF; else return q.front().I; } } L, R, M; void init() { for (int l = 1; l <= k; l++) { int sz = 0; for (int r = l; r <= k; r++) { int mx = p[r].II; for (int i = 1; i <= sz; i++) if (mx < tg[i]) swap(tg[i], mx); tg[++sz] = mx; f[l][r][0] = tg[1] - 1; f[l][r][1] = m - tg[sz]; for (int i = 1; i < sz; i++) f[l][r][2] = max(f[l][r][2], tg[i + 1] - tg[i] - 1); // cout << l << ' ' << r << ' ' << f[l][r][0] << ' ' << f[l][r][1] << ' ' << f[l][r][2] << '\n'; } } } void solve(int le) { if (le > ans) return; int sz = 0; for (int l = 1, r = 1; l <= k; l++) { while (r <= k && p[r].I <= p[l].I + le) { int val = p[r++].I; if (val > num[sz]) num[++sz] = val; } if (p[l].I + le + 1 > num[sz]) num[++sz] = p[l].I + le + 1; } for (int i = 1, l = 1, r = 1; i <= sz; i++) { while (l <= k && !(p[l].I <= num[i] && num[i] <= p[l].I + le)) l++; r = max(r, l); while (r <= k && p[r].I <= num[i] && num[i] <= p[r].I + le) r++; if (l > k) cur[i] = {INF, INF, INF}; else cur[i] = f[l][r - 1]; } for (int l = 1, r = 1; l <= sz; l++) { r = max(r, l); while (r <= sz && num[r] < num[l] + n) { L.add({cur[r][0], r}); R.add({cur[r][1], r}); M.add({cur[r][2], r++}); } // cout << le << ' ' << L.get() << ' ' << R.get() << ' ' << M.get() << '\n'; ans = min(ans, 1ll * le + 1ll * max(L.get() + R.get(), M.get())); L.del(l); R.del(l); M.del(l); } } int main() { for (int i = 1; i <= k; i++) cin >> p[i].I >> p[i].II; vector<int> t; sort(p + 1, p + k + 1); for (int i = 1; i <= k; i++) { t.pb(p[i].I - 1); t.pb(n - p[i].I); for (int j = 1; j <= k; j++) { t.pb(max(0, p[j].I - p[i].I - 1)); t.pb(p[i].I - 1 + n - p[j].I); } } sort(t.begin(), t.end()); t.resize(unique(t.begin(), t.end()) - t.begin()); // for (auto c : t) cout << c << ' ';cout << '\n'; init(); for (auto l : t) solve(l); cout << ans; return 0; } } int32_t main() { #define TASKNAME "" ios_base::sync_with_stdio(0); cin.tie(0); if (fopen(TASKNAME".inp","r" )) { freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".ans","w",stdout); } cin >> n >> m >> k; // if (max(n, m) <= 40) sub1 :: main(); else // if (k <= 25) sub2 :: main(); else sub3 :: main(); return 0; }

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

cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:316:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  316 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:317:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  317 |         freopen(TASKNAME".ans","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...