제출 #816974

#제출 시각아이디문제언어결과실행 시간메모리
816974finn__메기 농장 (IOI22_fish)C++17
44 / 100
1101 ms429076 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; constexpr size_t N = 3001; struct state { int64_t s, l, z; }; state f[N][N]; int64_t p[N][N]; long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) { // subtask 1 { bool all_even = 1; for (size_t i = 0; i < m; ++i) all_even &= !(x[i] & 1); if (all_even) { int64_t sum = 0; for (size_t i = 0; i < m; ++i) sum += w[i]; return sum; } } // subtask 2 { bool leq1 = 1; for (size_t i = 0; i < m; ++i) leq1 &= x[i] <= 1; if (leq1) { int64_t z = 0, t = 0; vector<pair<int, int>> zero, one; for (size_t i = 0; i < m; ++i) if (x[i]) one.emplace_back(y[i], w[i]), z += w[i]; else zero.emplace_back(y[i], w[i]), t += w[i]; if (n == 2) return max(t, z); sort(one.begin(), one.end()); sort(zero.begin(), zero.end()); int64_t ans = z; auto it = zero.begin(), jt = one.begin(); for (int i = 0; i <= n && (it != zero.end() || jt != one.end()); ++i) { if (it != zero.end() && it->first < i) z += it->second, ++it; if (jt != one.end() && jt->first < i) z -= jt->second, ++jt; ans = max(ans, z); } return ans; } } for (size_t i = 1; i < n; ++i) for (size_t j = 0; j < n; ++j) f[i][j].s = f[i][j].l = f[i][j].z = INT64_MIN / 2; for (size_t i = 0; i < m; ++i) p[x[i]][y[i] + 1] = w[i]; for (size_t i = 0; i < n; ++i) for (size_t j = 1; j <= n; ++j) p[i][j] += p[i][j - 1]; for (size_t i = 1; i < n; ++i) for (size_t j = 0; j <= n; ++j) { for (size_t k = 0; k < j; ++k) f[i][j].s = max(f[i][j].s, p[i - 1][j] - p[i - 1][k] + max(f[i - 1][k].s, f[i - 1][k].z)); for (size_t k = j; k <= n; ++k) f[i][j].s = max(f[i][j].s, f[i - 1][k].z); for (size_t k = j; k <= n; ++k) f[i][j].l = max(f[i][j].l, max(f[i - 1][k].l, f[i - 1][k].s) + p[i][k] - p[i][j]); f[i][j].z = max(f[i - 1][j].s, f[i - 1][j].l) + p[i][j]; if (!j) { for (size_t k = 0; k <= n; ++k) f[i][j].z = max(f[i][j].z, f[i - 1][k].z); } } int64_t ans = 0; for (size_t j = 0; j <= n; ++j) ans = max(ans, max(f[n - 1][j].s, max(f[n - 1][j].l, f[n - 1][j].z))); return ans; }

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

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:21:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
fish.cpp:26:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |             for (size_t i = 0; i < m; ++i)
      |                                ~~^~~
fish.cpp:35:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
fish.cpp:41:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             for (size_t i = 0; i < m; ++i)
      |                                ~~^~~
fish.cpp:68:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:69:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         for (size_t j = 0; j < n; ++j)
      |                            ~~^~~
fish.cpp:72:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
fish.cpp:74:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
fish.cpp:75:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         for (size_t j = 1; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:78:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
fish.cpp:79:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         for (size_t j = 0; j <= n; ++j)
      |                            ~~^~~~
fish.cpp:83:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |             for (size_t k = j; k <= n; ++k)
      |                                ~~^~~~
fish.cpp:86:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |             for (size_t k = j; k <= n; ++k)
      |                                ~~^~~~
fish.cpp:92:38: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |                 for (size_t k = 0; k <= n; ++k)
      |                                    ~~^~~~
fish.cpp:98:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     for (size_t j = 0; j <= n; ++j)
      |                        ~~^~~~
#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...