Submission #1075356

#TimeUsernameProblemLanguageResultExecution timeMemory
1075356qwerasdfzxclCultivation (JOI17_cultivation)C++17
0 / 100
2045 ms348 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll INF = 4e18; pair<ll, ll> P[303]; ll a[303], S[303], E[303], X[303], dp[303][303], L, U; int dq[303], n; ll solve(ll len){ // printf(" solve %lld\n", len); int sz = 0; for (int i=1,j=1;i<=n||j<=n;){ ll 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; ll e = min(a[i], a[j]+len); assert(j < i); if (sz > 0 && X[sz] == dp[j][i-1]) E[sz] = e; else{ ++sz; S[sz] = s, E[sz] = e, X[sz] = dp[j][i-1]; // printf(" fuck %d %d -> %lld\n", j, i-1, X[sz]); } } // for (int i=1;i<=sz;i++) printf(" (%lld, %lld, %lld)", S[i], E[i], X[i]); // printf("\n"); ll ret = INF; for (int i=1,j=1,pl=1,pr=1;i<=sz;i++){ while(pl < pr && dq[pl] < i) pl++; while(j <= sz && E[j-1]-S[i] < L){ while(pl < pr && X[dq[pr]] <= X[j]) pr--; dq[pr] = j; pr++, j++; } if (j > sz+1) break; assert(pl < pr); ret = min(ret, X[dq[pl]]); } return ret + len - 2; } int main(){ scanf("%lld %lld", &L, &U); scanf("%d", &n); for (int i=1;i<=n;i++) scanf("%lld %lld", &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--){ vector<ll> V; V.push_back(0); for (int j=n;j>=i;j--){ V.push_back(P[j].second); } V.push_back(U+1); sort(V.begin(), V.end()); for (int j=1;j<(int)V.size();j++) dp[i][n] = max(dp[i][n], V[j] - V[j-1]); // printf(" ok %d %d -> %lld\n", i, n, dp[i][n]); for (int j=n-1;j>=i;j--){ int idx = find(V.begin(), V.end(), P[j+1].second) - V.begin(); V.erase(V.begin() + idx); dp[i][j] = max(dp[i][j+1], V[idx+1] - V[idx]); // printf(" ok %d %d -> %lld\n", i, j, dp[i][j]); } } a[0] = 0, a[n+1] = L+1; ll mn = 0; for (int i=1;i<=n+1;i++) mn = max(mn, a[i] - a[i-1]); a[n+1] = INF; ll ans = INF; for (ll i=mn;i<=L;i++) ans = min(ans, solve(i)); cout << ans << '\n'; }

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%lld %lld", &L, &U);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cultivation.cpp:61:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...