제출 #965663

#제출 시각아이디문제언어결과실행 시간메모리
965663phoenix0423Garden (JOI23_garden)C++17
75 / 100
3041 ms196452 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #pragma GCC optimize("Ofast,unroll-loops") #define pb push_back #define eb emplace_back #define f first #define s second // #define int long long #define lowbit(x) x&-x namespace{ const int maxn = 5000 + 5; int a[maxn][maxn], dp[maxn][maxn], h[maxn], c[maxn], mx[maxn * 2], st[maxn * 2]; int n, m, d; int read() { int x = 0, w = 1; char ch = 0; while (ch < '0' || ch > '9') { // ch 不是数字时 if (ch == '-') w = -1; // 判断是否为负 ch = getchar(); // 继续读入 } while (ch >= '0' && ch <= '9') { // ch 是数字时 x = x * 10 + (ch - '0'); ch = getchar(); // 继续读入 } return x * w; // 数字 * 正负号 = 实际数值 } void main1(void){ fastio; n = read(), m = read(), d = read(); for(int i = 0; i < n; i++){ int x = read(), y = read(); h[x] = 1; c[y] = 1; } for(int i = 0; i < m; i++){ int x = read(), y = read(); a[x][y] = 1; } auto cal = [&](int x, int y) -> int { if(x <= 0 || y <= 0) return 0; return (x + y) * d - x * y; }; int ans = 0; for(int j = 2 * d - 1; j >= 0; j--){ int tj = j; if(j >= d) j -= d; if(c[j]){ j = tj; continue; } for(int i = 0; i < d; i++){ if(h[i] || a[i][j]) continue; dp[i][j] = dp[i][(j + 1) % d] + 1; } // if(j >= d){ // j = tj; // continue; // } int top = 0; for(int i = 0; i < 2 * d; i++){ while(top){ int cur = st[top]; if(dp[cur % d][j] <= dp[i % d][j]) break; int id = cur % d; top--; ans = max(ans, cal(dp[id][j], mx[cur] + (i - cur) - 1)); } mx[i] = (top ? i - st[top] : i + 1); st[++top] = i; } while(top){ int cur = st[top]; ans = max(ans, cal(dp[cur % d][j], mx[cur] + 2 * d - cur - 1)); top--; } j = tj; } ans = d * d - ans; int cur = 0; for(int i = d - 1; i >= 0; i--){ if(h[i]){ cur = i + 1; break; } } int tmp = d; for(int i = 0; i < d; i++){ tmp = min(tmp, cur); cur = (h[i] ? d : cur - 1); } cur = 0; for(int i = d - 1; i >= 0; i--){ if(c[i]){ cur = i + 1; break; } } for(int i = 0; i < d; i++){ tmp = min(tmp, cur); cur = (c[i] ? d : cur - 1); } ans = min(ans, d * tmp); cout<<ans<<"\n"; } } int main(){ main1(); }
#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...