이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
int ipow(int a, int n) {
if (n == 0) return 1;
int x = ipow(a, n/2);
if (n % 2 == 0) return x*x;
return x*x*a;
}
template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
for (auto elem : v)
stream << elem << " ";
return stream;
}
template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
for(auto &elem : v)
stream >> elem;
return stream;
}
long long smallN(int N, int M, vi X, vi Y,
vi W) {
ll maxY = 0;
for (int i = 0; i < M; i++) maxY = max(maxY, (ll)Y[i]);
maxY++;
vvl mat(N, vl(maxY+1));
for (int i = 0; i < M; i++) mat[X[i]][Y[i]] = W[i];
vector<vvl> dp(N, vvl(maxY+1, vl(maxY+1)));
ll _tmp1 = 0;
for (int j = 0; j <= maxY; j++) {
if (j > 0) _tmp1 += mat[0][j-1];
ll _tmp2 = 0;
for (int k = 0; k <= maxY; k++) {
if (k <= j) {
if (k > 0) _tmp2 -= mat[0][k-1];
} else {
if (k > 0) _tmp2 += mat[1][k-1];
}
dp[1][j][k] = _tmp1+_tmp2;
// cout << j << " " << k << " " << _tmp1+_tmp2 << nL;
}
}
for (int i = 2; i < N; i++) {
ll tmp1 = 0;
for (int j = 0; j <= maxY; j++) {
if (j > 0) tmp1 += mat[i-1][j-1];
ll tmp2 = 0;
for (int k = 0; k <= maxY; k++) {
if (k <= j) {
if (k > 0) tmp2 -= mat[i-1][k-1];
} else {
if (k > 0) tmp2 += mat[i][k-1];
}
ll tmp3 = 0;
for (int l = 0; l <= maxY;l++) {
if (l > k && l <= j) {
if (l > 0) tmp3 -= mat[i-1][l-1];
}
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+tmp1+tmp2+tmp3);
}
}
}
}
long long res = 0;
for (int i = 0; i <= maxY; i++) {
for (int j = 0; j <= maxY; j++)
res = max(res, dp[N-1][i][j]);
}
return res;
}
#define int long long
vector<vpll> col;
ll sum(ll x, ll y) {
ll res = 0;
for (auto [y_, w] : col[x]) {
if (y_ > y) break;
res += w;
}
return res;
}
#undef int
long long max_weights(int N, int M, vi X, vi Y,
vi W) {
#define int long long
ll maxY = 0;
for (int i = 0; i < M; i++) maxY = max(maxY, (ll)Y[i]);
maxY++;
// vvl mat(N, vl(maxY+1));
// for (int i = 0; i < M; i++) mat[X[i]][Y[i]] = W[i];
if (N <= 300 && maxY <= 10) return smallN(N, M, X, Y, W);
col = vector<vpll>(N);
for (int i = 0; i < M; i++) col[X[i]].pb({Y[i]+1, W[i]});
vector<vvl> dp(N, vvl(6, vl(6)));
vvi pos(N, {0});
for (int i = 0; i < M; i++) {
if (X[i]+1 < N) pos[X[i]+1].pb(Y[i]+1);
if (X[i]-1 >= 0) pos[X[i]-1].pb(Y[i]+1);
}
for (int i = 0; i < N; i++) {
sort(all(pos[i]));
sort(all(col[i]));
}
for (int j = 0; j < pos[1].size(); j++) {
for (int k = 0; k < pos[0].size(); k++) {
dp[1][j][k] = max(0LL, sum(0, pos[1][j])-sum(0, pos[0][k]))+max(0LL, sum(1, pos[0][k])-sum(1, pos[1][j]));
}
}
for (int i = 2; i < N; i++) {
for (int j = 0; j < pos[i].size(); j++) {
for (int k = 0; k < pos[i-1].size(); k++) {
for (int l = 0; l < pos[i-2].size();l++) {
ll res = max(0LL, sum(i, pos[i-1][k])-sum(i, pos[i][j]))+max(0LL, sum(i-1, pos[i][j])-max(sum(i-1, pos[i-2][l]),sum(i-1, pos[i-1][k])));
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+res);
// cout << i << ": " << pos[i-2][l] << " " << pos[i-1][k] << " " << pos[i][j] << " " << res << nL;
}
}
}
}
long long res = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
res = max(res, dp[N-1][i][j]);
}
}
#undef int
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
fish.cpp: In function 'long long int max_weights(int, int, vi, vi, vi)':
fish.cpp:145:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int j = 0; j < pos[1].size(); j++) {
| ~~^~~~~~~~~~~~~~~
fish.cpp:146:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int k = 0; k < pos[0].size(); k++) {
| ~~^~~~~~~~~~~~~~~
fish.cpp:152:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int j = 0; j < pos[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
fish.cpp:153:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (int k = 0; k < pos[i-1].size(); k++) {
| ~~^~~~~~~~~~~~~~~~~
fish.cpp:154:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for (int l = 0; l < pos[i-2].size();l++) {
| ~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |