Submission #965660

#	Time	Username	Problem	Language	Result	Execution time	Memory
965660		phoenix0423	Garden (JOI23_garden)	C++17	100 / 100	2988 ms	201392 KiB

garden

#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;
            int nxt = j == d - 1 ? 0 : j + 1;
            dp[i][j] = dp[i][nxt] + 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 - (cur >= d ? d : 0)][j] <= dp[i - (i >= d ? d : 0)][j]) break;
                int id = cur - (cur >= d ? d : 0); 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 - (cur >= d ? d : 0)][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();
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25