제출 #720843

#제출 시각아이디문제언어결과실행 시간메모리
720843HaiHoang메기 농장 (IOI22_fish)C++17
53 / 100
523 ms888128 KiB
#include <bits/stdc++.h> using namespace std; #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for (int i = 0, _n = n; i < _n; ++i) #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it) template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; } template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; } const int MAXN = 1e5 + 5; namespace sub1 { bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { REP(i, M) if(X[i] % 2 == 1) return false; return true; } long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { long long ans = 0; REP(i, M) ans += W[i]; return ans; } } namespace sub2 { long long pre[2][MAXN]; bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { REP(i, M) if(X[i] > 1) return false; return true; } long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { long long ans = 0; REP(i, M) pre[X[i]][Y[i]] += W[i]; FOR(i, 1, N - 1) { pre[0][i] += pre[0][i - 1]; pre[1][i] += pre[1][i - 1]; } ans = max(pre[0][N - 1], pre[1][N - 1]); if(N == 2) return ans; REP(i, N) { long long val = pre[1][N - 1] - pre[1][i]; maximize(ans, val + pre[0][i]); } return ans; } } namespace sub3 { bool check (int N, int M, vector <int> X, vector <int> Y, vector <int> W) { REP(i, M) if(Y[i]) return false; return true; } long long dp[MAXN][2][2], a[MAXN]; long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { long long ans = 0; REP(i, M) a[X[i] + 1] += W[i]; FOR(i, 1, N) { dp[i][1][0] = max({dp[i - 1][0][0] + a[i - 1] + a[i + 1], dp[i - 1][0][1] + a[i + 1], dp[i - 1][1][0] - a[i] + a[i + 1]}); dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][0][1]); dp[i][0][1] = dp[i - 1][1][0]; maximize(ans, dp[i][1][0]); maximize(ans, dp[i][0][0]); maximize(ans, dp[i][0][1]); // cout << dp[i][1][0] << " \n"[i == N]; } return ans; } } namespace sub4 { bool check (int N, int M, vector <int> X, vector <int> Y, vector <int> W) { if(N > 300) return false; REP(i, M) if(Y[i] > 8) return false; return true; } long long dp[MAXN][10][10], pre[MAXN][10]; long long get(int x, int l, int r) { if(l > r) return 0; return pre[x][r] - pre[x][l - 1]; } long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { long long ans = 0; int lim = min(9, N + 1); REP(i, M) pre[X[i] + 1][Y[i] + 1] += W[i]; FOR(i, 1, N) FOR(j, 1, lim - 1) pre[i][j] += pre[i][j - 1]; FOR(i, 2, N) REP(l1, lim) REP(l2, lim) REP(l3, lim) { long long val = 0, val2 = 0; if(l2 < l3) val = get(i - 1, l2 + 1, l3); else val = get(i, l3 + 1, l2); if(l1 > l2 && l2 < l3) { if(l1 < l3) maximize(dp[i][l2][l3], dp[i - 1][l1][l2] + get(i - 1, l1 + 1, l3)); else maximize(dp[i][l2][l3], dp[i - 1][l1][l2]); } else maximize(dp[i][l2][l3], dp[i - 1][l1][l2] + val); maximize(ans, dp[i][l2][l3]); } return ans; } } namespace sub5 { const int MAX = 305; long long dp[MAX][MAX][MAX], Max[3][MAX][MAX][MAX]; long long pre[MAX][MAX]; long long get(int i, int l, int r) { if(r < l) return 0; return pre[i][r] - pre[i][l - 1]; } long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { long long ans = 0; memset(Max, -0x3f, sizeof Max); REP(i, M) pre[X[i] + 1][Y[i] + 1] += W[i]; FOR(i, 1, N) FOR(j, 1, N) pre[i][j] += pre[i][j - 1]; REP(i, 3) memset(Max[i][1], 0, sizeof Max[i][1]); FOR(i, 2, N) { REP(l1, N + 1) REP(l2, N + 1) { if(l1 < l2) dp[i][l1][l2] = Max[0][i - 1][l1][l1] + get(i - 1, l1 + 1, l2); else dp[i][l1][l2] = Max[0][i - 1][N][l1] + get(i, l2 + 1, l1); if(l1 < l2) { maximize(dp[i][l1][l2], Max[1][i - 1][l2][l1]); // maximize(dp[i][l1][l2], Max[2][i - 1][l2][l1] + get(i - 1, 1, l2)); } maximize(ans, dp[i][l1][l2]); maximize(Max[0][i][l1][l2], dp[i][l1][l2]); maximize(Max[2][i][l1][l2], dp[i][l1][l2] - get(i, 1, max(l1, l2))); if(l1 > 0) { maximize(Max[0][i][l1][l2], Max[0][i][l1 - 1][l2]); maximize(Max[2][i][l1][l2], Max[2][i][l1 - 1][l2]); } } FORD(l1, N, 0) FORD(l2, l1, 0) { maximize(Max[1][i][l1][l2], dp[i][l1][l2]); if(l1 < N) maximize(Max[1][i][l1][l2], Max[1][i][l1 + 1][l2]); } } // cout << dp[5][0][4] << '\n'; // cout << Max[2][2][5][3] << '\n'; return ans; } } long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { if(N <= 300) return sub5::Main(N, M, X, Y, W); if(sub1::check(N, M, X, Y, W)) return sub1::Main(N, M, X, Y, W); if(sub2::check(N, M, X, Y, W)) return sub2::Main(N, M, X, Y, W); if(sub3::check(N, M, X, Y, W)) return sub3::Main(N, M, X, Y, W); if(sub4::check(N, M, X, Y, W)) return sub4::Main(N, M, X, Y, W); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int sub4::Main(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:85:32: warning: unused variable 'val2' [-Wunused-variable]
   85 |             long long val = 0, val2 = 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...