이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second
const int N=100005;
vector<ll> pr[N];
vector<pi> f[N];
ll sum(int i, int j) {
int l=0, r=f[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (f[i][m-1].f>j) r=m-1;
else l=m;
}
return pr[i][r];
}
vector<pi> dp[N], dp2[N], dp3[N];
vector<ll> prmx[N], prmx2[N], sfmx[N];
ll prmxquery(int i, int j) {
int l=0, r=dp[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (dp[i][m-1].f > j) r=m-1;
else l=m;
}
return prmx[i][r];
}
ll prmx2query(int i, int j) {
int l=0, r=dp3[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (dp3[i][m-1].f >= j) r=m-1;
else l=m;
}
return prmx2[i][r];
}
ll sfmxquery(int i, int j) {
return sfmx[i][0];
int l=0, r=dp2[i].size();
while (l<r) {
int m=(l+r)>>1;
if (dp2[i][m].f<j) l=m+1;
else r=m;
}
return sfmx[i][r];
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
forn(i,m) {
f[x[i]+1].pb({y[i]+1,w[i]});
}
for(int i=1;i<=n;++i) {
sort(all(f[i]));
f[i].pb({n+1,0});
pr[i]={0};
forn(j,f[i].size()) pr[i].pb(pr[i].back()+f[i][j].s);
}
dp[0].pb({0,0});
dp[0].pb({n,0});
pr[0]={0,0,0};
dp2[0]=dp3[0]=dp[0];
prmx[0]={0,0};
prmx2[0]=sfmx[0]=prmx[0];
pr[n+1]={0,0,0};
for(int i=1; i<=n; ++i) {
if (f[i][0].f!=1) {
int j=0;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
for(auto&x:f[i]) {
int j=x.f-1;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
prmx[i]={-1000000000000000000ll};
prmx2[i]=sfmx[i]=prmx[i];
for (int j=0; j<dp[i].size(); ++j) {
prmx[i].pb(max(prmx[i].back(),dp[i][j].s));
prmx2[i].pb(max(prmx2[i].back(),dp3[i][j].s-sum(i,dp3[i][j].f)));
}
reverse(all(dp2[i]));
for (int j=0; j<dp2[i].size(); ++j) {
sfmx[i].pb(max(sfmx[i].back(),dp2[i][j].s));
}
reverse(all(dp2[i]));
reverse(all(sfmx[i]));
}
ll ans=0;
for(auto&x:dp[n]) ans=max(ans,x.s);
return ans;
return prmx[n].back();
}
컴파일 시 표준 에러 (stderr) 메시지
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define forn(i,n) for(int i=0;i<n;++i)
......
68 | forn(j,f[i].size()) pr[i].pb(pr[i].back()+f[i][j].s);
| ~~~~~~~~~~~~~
fish.cpp:68:5: note: in expansion of macro 'forn'
68 | forn(j,f[i].size()) pr[i].pb(pr[i].back()+f[i][j].s);
| ^~~~
fish.cpp:121:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int j=0; j<dp[i].size(); ++j) {
| ~^~~~~~~~~~~~~
fish.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int j=0; j<dp2[i].size(); ++j) {
| ~^~~~~~~~~~~~~~
# | 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... |