Submission #1174702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174702		mmmmge1234	Cultivation (JOI17_cultivation)	C++20	100 / 100	1137 ms	4796 KiB

cultivation

#include <bits/stdc++.h>
using namespace std;

#define st first
#define nd second

const long long INF = 4e18;

pair<long long, long long> P[303];
long long a[303], S[707], E[707], X[3][707], dp[303][303], F[2][303][303], L, U;
int dq[3][707], n;

pair<long long, int> V[303];
int f[303], g[303];

long long solve(long long len){
        int sz = 0;

        for(int i = 1, j = 1; i <= n || j <= n;){
                long long s = min(a[i], a[j] + len);
                while(a[i] == s || a[j] + len == s){
                        if(a[i] == s) i++;
                        if(a[j] + len == s) j++;
                }

                if(j > n) break;
                long long e = min(a[i], a[j] + len);

                assert(j < i);

                sz++;
                S[sz] = s, E[sz] = e;
                X[0][sz] = F[0][j][i - 1], X[1][sz] = F[1][j][i - 1], X[2][sz] = dp[j][i - 1];
        }

        long long ret = INF;
        int pl[3] ={1, 1, 1}, pr[3] ={1, 1, 1};

        for(int i = 1, j = 1; i <= sz; i++){
                for(int z = 0; z < 3; z++) while(pl[z] < pr[z] && dq[z][pl[z]] < i) pl[z]++;
                while(j <= sz && E[j - 1] - S[i] < L){
                        for(int z = 0; z < 3; z++){
                                while(pl[z] < pr[z] && X[z][dq[z][pr[z] - 1]] <= X[z][j]) pr[z]--;
                                dq[z][pr[z]] = j;
                                pr[z]++;
                        }
                        j++;
                }

                if(j > sz && E[j - 1] - S[i] < L) break;
                for(int z = 0; z < 3; z++) assert(pl[z] < pr[z]);

                ret = min(ret, max(X[0][dq[0][pl[0]]] + X[1][dq[1][pl[1]]], X[2][dq[2][pl[2]]]));
        }

        return ret + len - 1;
}

int main(){
        if(fopen("csort.inp", "r")){
                freopen("csort.inp", "r", stdin);
                freopen("csort.out", "w", stdout);
        }
        cin.tie(0)->sync_with_stdio(0);
        cout.tie(0)->sync_with_stdio(0);
        cin >> L >> U;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> P[i].first >> P[i].second;
        sort(P + 1, P + n + 1);

        for(int i = 1; i <= n; i++) a[i] = P[i].first;
        for(int i = n; i > 0; i--){
                int sz = 0;
                V[sz++] ={0, 0};
                for(int j = n; j >= i; j--){
                        V[sz++] ={P[j].second, j};
                }
                V[sz++] ={U + 1, n + 1};
                sort(V, V + sz);

                for(int i = 0; i < sz - 1; i++) f[V[i].second] = V[i + 1].second, g[V[i + 1].second] = V[i].second;

                for(int j = 1; j < sz; j++) dp[i][n] = max(dp[i][n], V[j].first - V[j - 1].first - 1);
                F[0][i][n] = P[f[0]].second - 1;
                F[1][i][n] = U - P[g[n + 1]].second;

                for(int j = n - 1; j >= i; j--){
                        int ff = f[j + 1], gg = g[j + 1];
                        g[ff] = gg;
                        f[gg] = ff;

                        dp[i][j] = max(dp[i][j + 1], P[ff].second - P[gg].second - 1);
                        F[0][i][j] = P[f[0]].second - 1;
                        F[1][i][j] = U - P[g[n + 1]].second;
                }
        }

        long long mn = 0;
        for(int i = 2; i <= n; i++) mn = max(mn, a[i] - a[i - 1]);
        mn = max(mn,(L - a[n]) + a[1]);
        a[n + 1] = INF;

        long long ans = INF;
        vector<long long> C ={L};
        for(int i = 1; i <= n; i++){
                for(int j = i + 1; j <= n; j++){
                        if(a[j] - a[i] >= mn) C.push_back(a[j] - a[i]);
                        if(L - a[j] + a[i] >= mn) C.push_back(L - a[j] + a[i]);
                        if(L + a[j] - a[i] >= mn) C.push_back(L + a[j] - a[i]);
                }
        }
        sort(C.begin(), C.end());
        C.erase(unique(C.begin(), C.end()), C.end());
        for(long long x : C) ans = min(ans, solve(x));
        cout << ans << '\n';
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen("csort.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |                 freopen("csort.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 20 / 20