제출 #627695

#제출 시각아이디문제언어결과실행 시간메모리
627695tutis메기 농장 (IOI22_fish)C++17
35 / 100
1103 ms2097152 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; using ll = long long; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { vector<pair<int, ll>>P[N]; for (int i = 0; i < M; i++) P[X[i]].push_back({Y[i], W[i]}); for (int i = 0; i < N; i++) sort(P[i].begin(), P[i].end()); for (int i = 0; i < N; i++) { P[i].push_back({N, 0}); for (int j = 1; j < (int)P[i].size(); j++) P[i][j].second += P[i][j - 1].second; } int ret = 0; ll dp[N]; ll u[N][N]; ll d[N][N]; ll u1[N][N]; ll d1[N][N]; auto get = [&](int x, int y)->ll { if (x < 0 || x >= N) return 0; auto it = lower_bound(P[x].begin(), P[x].end(), make_pair(y + 1, -1ll)); if (it == P[x].begin()) return 0; it--; return it->second; }; for (int x = 0; x < N; x++) { dp[x] = 0; for (int y = 0; y < N; y++) { u[x][y] = d[x][y] = 0; u1[x][y] = u[x][y] - get(x, y); d1[x][y] = d[x][y] + get(x + 1, y); } ll sum = 0; int i = 0; if (x == 0) continue; for (int y = 0; y < N; y++) { u[x][y] = dp[x - 1]; u[x][y] = max(u[x][y], get(x - 1, y) + (x - 2 >= 0 ? dp[x - 2] : 0ll)); u[x][y] -= get(x - 1, y); for (int y1 = 0; y1 <= y; y1++) u[x][y] = max(u[x][y], u1[x - 1][y1]); u[x][y] += get(x - 1, y); } for (int y = 0; y < N; y++) u1[x][y] = u[x][y] - get(x, y); d[x][N - 1] = u[x][N - 1]; for (int y = N - 1; y >= 0; y--) { d[x][y] += get(x, y); for (int y1 = y; y1 < N; y1++) d[x][y] = max(d[x][y], d1[x - 1][y1]); d[x][y] -= get(x, y); } for (int y = N - 1; y >= 0; y--) d1[x][y] = d[x][y] + get(x + 1, y); dp[x] = dp[x - 1]; dp[x] = max(dp[x], get(x, N - 1) + u[x - 1][N - 1]); dp[x] = max(dp[x], u[x][N - 1]); for (int y = 0; y < N; y++) { dp[x] = max(dp[x], d1[x - 1][y]); dp[x] = max(dp[x], d[x][y]); } } return dp[N - 1]; }

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

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:12: warning: unused variable 'sum' [-Wunused-variable]
   44 |         ll sum = 0;
      |            ^~~
fish.cpp:45:13: warning: unused variable 'i' [-Wunused-variable]
   45 |         int i = 0;
      |             ^
fish.cpp:19:9: warning: unused variable 'ret' [-Wunused-variable]
   19 |     int ret = 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...