제출 #629278

#제출 시각아이디문제언어결과실행 시간메모리
629278qwerasdfzxcl메기 농장 (IOI22_fish)C++17
18 / 100
828 ms132180 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 4e18; vector<int> H[100100], A[100100]; vector<ll> dp[2][100100], S[100100], prf[2][100100], suf[2][100100]; int n, sz[100100]; ll cost(int i, int s, int e){ if (s>e || i==0) return 0; int j1 = upper_bound(H[i].begin(), H[i].end(), s-1) - H[i].begin() - 1; int j2 = upper_bound(H[i].begin(), H[i].end(), e) - H[i].begin() - 1; return S[i][j2] - S[i][j1]; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { n = N; for (int i=0;i<=N;i++) {H[i].push_back(0); H[i].push_back(N);} for (int i=0;i<M;i++){ ++X[i], ++Y[i]; H[X[i]].push_back(Y[i]); H[X[i]].push_back(Y[i]-1); if (X[i]>1) H[X[i]-1].push_back(Y[i]); if (X[i]<N) H[X[i]+1].push_back(Y[i]); } for (int i=0;i<=N;i++){ sort(H[i].begin(), H[i].end()); H[i].erase(unique(H[i].begin(), H[i].end()), H[i].end()); sz[i] = H[i].size(); A[i].resize(sz[i], 0); S[i].resize(sz[i], 0); dp[0][i].resize(sz[i], 0); dp[1][i].resize(sz[i], 0); prf[0][i].resize(sz[i]); prf[1][i].resize(sz[i]); suf[0][i].resize(sz[i]); suf[1][i].resize(sz[i]); } for (int i=0;i<M;i++){ int idx = lower_bound(H[X[i]].begin(), H[X[i]].end(), Y[i]) - H[X[i]].begin(); assert(idx < sz[X[i]]); A[X[i]][idx] = W[i]; } for (int i=1;i<=n;i++){ for (int j=1;j<sz[i];j++) S[i][j] = S[i][j-1] + A[i][j]; } dp[0][0][0] = 0; dp[1][0][0] = 0; assert(sz[0]==2); dp[0][0][1] = -INF; dp[1][0][1] = -INF; for (int i=1;i<=n;i++){ --i; for (int j=0;j<sz[i];j++){ prf[0][i][j] = dp[0][i][j] + cost(i, H[i][j]+1, n); prf[1][i][j] = max(dp[0][i][j], dp[1][i][j]); suf[0][i][j] = max(dp[0][i][j], dp[1][i][j]) + cost(i+1, 1, H[i][j]); suf[1][i][j] = dp[1][i][j] + cost(i+1, 1, H[i][j]); if (j==0) continue; prf[0][i][j] = max(prf[0][i][j], prf[0][i][j-1]); prf[1][i][j] = max(prf[1][i][j], prf[1][i][j-1]); suf[0][i][j] = max(suf[0][i][j], suf[0][i][j-1]); suf[1][i][j] = max(suf[1][i][j], suf[1][i][j-1]); } ++i; for (int j=0;j<sz[i];j++){ ///0 -> 0 int idx00 = upper_bound(H[i-1].begin(), H[i-1].end(), H[i][j]) - H[i-1].begin() - 1; dp[0][i][j] = max(dp[0][i][j], prf[0][i-1][idx00] - cost(i-1, H[i][j]+1, n)); /*for (int k=0;k<sz[i-1] && H[i-1][k]<=H[i][j];k++){ dp[0][i][j] = max(dp[0][i][j], dp[0][i-1][k] + cost(i-1, H[i-1][k]+1, H[i][j])); }*/ ///1 -> 0 if (i>=2){ int idx10 = upper_bound(H[i-2].begin(), H[i-2].end(), H[i][j]) - H[i-2].begin() - 1; dp[0][i][j] = max(dp[0][i][j], prf[1][i-2][idx10] + cost(i-1, 1, H[i][j])); if (idx10+1 < sz[i-2]) dp[0][i][j] = max(dp[0][i][j], suf[0][i-2][idx10+1]); /*for (int k=0;k<sz[i-2];k++){ dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-2][k], dp[1][i-2][k]) + cost(i-1, 1, max(H[i-2][k], H[i][j]))); }*/ } ///0 -> 1 dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][sz[i-1]-1] + cost(i, H[i][j]+1, n)); ///1 -> 1 int idx11 = lower_bound(H[i-1].begin(), H[i-1].end(), H[i][j]) - H[i-1].begin(); dp[1][i][j] = max(dp[1][i][j], suf[1][i-1][idx11] - cost(i, 1, H[i][j])); //for (int k=0;k<sz[i-1];k++) if (H[i-1][k] >= H[i][j]) dp[1][i][j] = max(dp[1][i][j], dp[1][i-1][k] + cost(i, H[i][j]+1, H[i-1][k])); } } //printf(" %lld %lld %lld\n", H[1][0], H[1][1], H[1][2]); //printf(" %lld -> %lld(%d)\n", cost(1, 1, 1), dp[0][2][1], H[2][1]); return max(*max_element(dp[0][n].begin(), dp[0][n].end()), *max_element(dp[1][n].begin(), dp[1][n].end())); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...