제출 #843970

#제출 시각아이디문제언어결과실행 시간메모리
843970Dextar메기 농장 (IOI22_fish)C++17
70 / 100
891 ms2097152 KiB
#include <cstdio> #ifdef DEBUG #define D(X) X #else #define D(X) #endif #include <bits/stdc++.h> #define F first #define S second #define ll long long #define pi 3.14159265359 #define pub push_back #define pob pop_back #define pari pair<int,int> #define parli pair<long, long> using namespace std; /* 4 8 1 1 1 1 0 0 0 0 0 1 2 3 0 1 2 3 1 3 1 4 2 5 1 1 */ const int INF = 1000 * 1000 * 1000; const int mod = 1000 * 1000 * 1000 + 7; ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) { vector<vector<ll>> cnt2(3, vector<ll>(n+1, 0)); vector<vector<ll>> cnt3(n+1, vector<ll>(3, 0)); int odd = 0, mx = 0, mxy = 0; ll all = 0; for(int i=0; i<m; i++) { if(x[i]%2==1) { odd = 1; } if(x[i]<=1) cnt2[x[i]][y[i]+1] += w[i]; if(y[i]==0) { cnt3[x[i]][y[i]+1] += w[i]; } all += w[i]; mx = max(mx, x[i]); mxy = max(mxy, y[i]); } if(!odd) { return all; } for(int i=0; i<2; i++) { for(int j=1; j<=n; j++) { cnt2[i][j] += cnt2[i][j-1]; } } /* for(int i=0; i<2; i++) { for(int j=0; j<=n; j++) { cout<<cnt2[i][j]<<" "; } cout<<endl; } */ if(mx<=1) { if(n==2) { return max(cnt2[0][n], cnt2[1][n]); } else { ll res = cnt2[1][n], best = res; for(int j=1; j<=n; j++) { best = max(best, res+cnt2[0][j]-cnt2[1][j]); //cout<<res<<" "<<cnt2[0][j]<<" "<< } return best; } } if(mxy==0) { vector<vector<ll>> dp(n+7, vector<ll>(2,0)); for(int i=n-2; i>=0; i--) { dp[i][0] = max(dp[i+1][0], dp[i+1][1] + cnt3[i][1]); dp[i][1] = max(dp[i+1][1], max(dp[i+1][0], dp[i+2][0]+cnt3[i+1][1])); } return max(dp[0][0], dp[0][1]); } vector<vector<ll>> cnt(n + 1, vector<ll>(n+1, 0)); for(int i=0; i<m; i++) { cnt[x[i]][y[i]+1] += w[i]; } for(int i=0; i<n; i++) { for(int j=1; j<=n; j++) { cnt[i][j] += cnt[i][j-1]; } } vector<vector<ll>> pref(n+1, vector<ll>(n+1, 0)); vector<vector<ll>> suf(n+1, vector<ll>(n+1, 0)); vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(2, 0))); ll res = 0; for(int i=1; i<n; i++) { if(i==1) { pref[i-1][0] = 0; } else { pref[i-1][0] = dp[i-2][0][0]; } for(int j=1; j<=n; j++) { pref[i-1][j] = max(pref[i-1][j-1], dp[i-1][j][1] - cnt[i-1][j]); } suf[i-1][n] = cnt[i][n] + max(dp[i-1][n][0], dp[i-1][n][1]); for(int j=n-1; j>=1; j--) { suf[i-1][j] = max(suf[i-1][j+1], max(dp[i-1][j][0], dp[i-1][j][1]) + cnt[i][j]); } dp[i][0][0] = dp[i][0][1] = max(suf[i-1][1], dp[i-1][0][0]); for(int j=1; j<=n; j++) { dp[i][j][0] = suf[i-1][j] - cnt[i][j]; dp[i][j][1] = cnt[i-1][j] + pref[i-1][j]; if(i>1) { dp[i][j][1] = max(dp[i][j][1], cnt[i-1][j]+pref[i-2][j]); dp[i][j][1] = max(dp[i][j][1], suf[i-2][j]); } //res = max(res, max(dp[i][j][0], dp[i][j][1])); } } for(int i=0; i<n; i++) for(int j=0; j<=n; j++) { for(int bin=0; bin<2; bin++) res = max(res, dp[i][j][bin]); } return res; } /* int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); D(freopen("input.txt","r",stdin);) //D(freopen("ouput.txt","w",stdout);) int t = 1; //cin >> t; loop: while(t--) { int n, m; cin >> n >> m; vector<int> x(m), y(m), w(m); for(int i=0; i<m; i++) { cin >> x[i]; } for(int i=0; i<m; i++) { cin >> y[i]; } for(int i=0; i<m; i++) { cin >> w[i]; } ll res = max_weights(n, m, x, y, w); cout << res; } return 0; } */
#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...