| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 835527 | HappyPacMan | Garden (JOI23_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXD = 5e3;
bool checked[MAXD][MAXD];
int minimum_cells(int N, int M, int D, vector<int> P, vector<int> Q, vector<int> R, vector<int> S) {
short cnt[D],must[D];
vector<short> base[D];
vector<pair<short,short> > added[D];
memset(cnt,0,sizeof(cnt));
memset(must,0,sizeof(must));
short nxt[2*D],rev[2*D];
for(int i=0;i<M;i++){
checked[S[i]][R[i]] = true;
}
for(int i=0;i<D;i++){
for(int j=0;j<D;j++){
if(checked[i][j]){
base[i].push_back(j);
}
}
if(base[i].size()){
for(int j=0,k=0;j<D;j++){
added[j].emplace_back(i,base[i][(k-1+base[i].size())%base[i].size()]);
if(j == base[i][k]){
k++;
}
}
}
}
for(int i=0;i<N;i++){
must[P[i]] = true;
cnt[Q[i]] = true;
}
short aaa = 0;
for(short i=0;i<D;i++){
aaa += must[i];
}
int ans = INF;
for(short i=0;i<D;i++){
memset(nxt,-1,sizeof(nxt));
memset(rev,-1,sizeof(rev));
vector<short> calc[D];
for(auto [x,y] : added[i]){
calc[y].push_back(x);
}
for(short j=0;j<D;j++){
for(short it : calc[j]){
cnt[it]++;
}
}
vector<short> st;
for(short j=0;j<D;j++){
if(cnt[j]){
st.push_back(j);
}
}
for(short j=0;j<D;j++){
if(cnt[j]){
st.push_back(j+D);
}
}
short last = -1, dist = 0;
for(short it : st){
if(last != -1){
nxt[last] = it;
rev[it] = last;
dist = max(dist,(short)(it-last));
}
last = it;
}
short sum = 0;
for(short j=0;j<D;j++){
short k = i+j;
if(k >= D){
k -= D;
}
for(short it : calc[k]){
cnt[it]--;
if(cnt[it] == 0){
if(rev[it] != -1){
nxt[rev[it]] = nxt[it];
}
if(nxt[it] != -1){
rev[nxt[it]] = rev[it];
}
if(rev[it] != -1 && nxt[it] != -1){
dist = max(dist,(short)(nxt[it]-rev[it]));
}
if(rev[it+D] != -1){
nxt[rev[it+D]] = nxt[it+D];
}
if(nxt[it] != -1){
rev[nxt[it+D]] = rev[it+D];
}
if(rev[it+D] != -1 && nxt[it+D] != -1){
dist = max(dist,(short)(nxt[it+D]-rev[it+D]));
}
}
}
sum += must[k];
if(sum == aaa){
ans = min(ans,(j+1)*(D-dist+1));
}
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,M,D;
cin >> N >> M >> D;
vector<int> P(N),Q(N),R(M),S(M);
for(int i=0;i<N;i++){
cin >> P[i] >> Q[i];
}
for(int j=0;j<M;j++){
cin >> R[i] >> S[i];
}
cout << minimum_cells(N,M,D,P,Q,R,S) << "\n";
}