제출 #965594

#제출 시각아이디문제언어결과실행 시간메모리
965594phoenix0423Garden (JOI23_garden)C++17
0 / 100
290 ms120152 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") #define pb push_back #define eb emplace_back #define f first #define s second #define int long long #define lowbit(x) x&-x const int maxn = 5000 + 5; const int INF = 1e18; int a[maxn][maxn], dp[maxn * 2][maxn], h[maxn], c[maxn]; signed main(void){ // fastio; int n, m, d; cin>>n>>m>>d; set<int> cx, cy; for(int i = 0; i < n; i++){ int x, y; cin>>x>>y; cx.insert(x), cy.insert(y); h[x] |= 1; c[y] |= 1; } for(int i = 0; i < m; i++){ int x, y; cin>>x>>y; a[x][y] |= 2; // h[x] |= 2, c[y] |= 2; } auto cal = [&](int x, int y) -> int { if(x <= 0 || y <= 0) return 0; // cout<<"cal : "<<x<<" "<<y<<"\n"; y = min(y, d - 1); x = min(x, d - 1); return (x + y) * d - x * y; }; int ans = 0; for(int j = d - 1; j >= 0; j--){ if(c[j]) continue; for(int i = 0; i < d; i++){ if(h[i] || a[i][j]) continue; dp[i][j] = dp[i][j + 1] + 1; // cout<<"ok : "<<i<<" "<<j<<" "<<dp[i][j]<<"\n"; } for(int i = d; i < 2 * d; i++) dp[i][j] = dp[i - d][j]; vector<int> st; for(int i = 0; i < 2 * d; i++){ int pos = i; while(st.size() && dp[st.back()][j] > dp[i][j]){ int id = st.back(); st.pop_back(); pos = id; ans = max(ans, cal(dp[id][j], (i - id))); } if(st.empty()) dp[0][j] = dp[i][j]; else dp[pos][j] = dp[i][j]; st.pb(pos); } while(!st.empty()){ ans = max(ans, cal(dp[st.back()][j], 2 * d - st.back())); st.pop_back(); } for(int i = 0; i < d; i++){ if(h[i] || a[i][j]) continue; dp[i][j] = dp[i][j + 1] + 1; // cout<<"ok : "<<i<<" "<<j<<" "<<dp[i][j]<<"\n"; } } ans = d * d - ans; int cur = *(cx.rbegin()) + 1; int id = 0; for(int i = 0; i < d; i++){ ans = min(ans, d * cur); if(!cx.count(i)) cur--; else cur = d; } ans = min(ans, d * cur); cur = *(cy.rbegin()) + 1; for(int i = 0; i < d; i++){ ans = min(ans, d * cur); if(!cy.count(i)) cur--; else cur = d; } ans = min(ans, d * cur); cout<<ans<<"\n"; }

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

garden.cpp: In function 'int main()':
garden.cpp:75:9: warning: unused variable 'id' [-Wunused-variable]
   75 |     int id = 0;
      |         ^~
#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...