#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define V vector
#define pb push_back
struct segtree{
private:
struct node{
ll maxd;
};
node single(ll v){
return {v};
}
node neutral={LLONG_MIN};
node merge(node a,node b){
return{max(a.maxd, b.maxd)};
}
public:
int size;
V<node>query;
void init(int n){
size=1;
while(size<n)size*=2;
query.assign(2*size,neutral);
}
void build(V<ll>&a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<a.size()){
query[x]=single(a[lx]);
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void build(V<ll>&a){
build(a,0,0,size);
}
node calc(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l)
return neutral;
if(l<=lx && rx<=r)
return query[x];
int m=(lx+rx)/2;
node a=calc(l,r,2*x+1,lx,m);
node b=calc(l,r,2*x+2,m,rx);
return merge(a,b);
}
long long calc(int l,int r){
return calc(l,r,0,0,size).maxd;
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
vector<vector<long long >>grid(N+1,vector<long long>(N+1,0));
for(int i=0;i<M;i++){
grid[X[i]][Y[i]+1]+=W[i];
}
for(int i=0;i<N;i++){
for(int j=1;j<=N;j++){
grid[i][j]+=grid[i][j-1];
}
}
V<V<V<ll>>>dp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
V<V<V<ll>>>vp(N,V<V<ll>>(N+1,V<ll>(N+1,0)));
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
dp[0][i][j]=max(0LL,grid[0][j]-grid[0][i]);
vp[0][i][j]=dp[0][i][j]+max(0LL,grid[1][i]-grid[1][j]);
}
}
for(int i=1;i<N;i++){
for(int j=0;j<=N;j++){
V<ll>a;
for(int g=0;g<=N;g++)
a.pb(dp[i-1][g][j]);
segtree tree_dp;
tree_dp.init(N+1);
tree_dp.build(a);
V<ll>b;
for(int g=0;g<=N;g++)
b.pb(vp[i-1][g][j]);
segtree tree_vp;
tree_vp.init(N+1);
tree_vp.build(b);
for(int g=0;g<=N;g++){
if(g<=j){
dp[i][j][g]=tree_vp.calc(0,N+1);
}
else{
dp[i][j][g]=max(tree_dp.calc(0,g+1)+grid[i][g]-grid[i][j],tree_vp.calc(g,N+1));
}
vp[i][j][g]=dp[i][j][g]+max(0LL,grid[i+1][j]-grid[i+1][g]);
}
}
}
ll ans=LLONG_MIN;
for(int i=0;i<=N;i++){
ans=max(ans,dp[N-1][i][0]);
}
return ans;
}
Compilation message
fish.cpp: In member function 'void segtree::build(std::vector<long long int>&, int, int, int)':
fish.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if(lx<a.size()){
| ~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
883 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
838 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
356 KB |
Output is correct |
| 2 |
Correct |
0 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
356 KB |
Output is correct |
| 7 |
Correct |
0 ms |
440 KB |
Output is correct |
| 8 |
Correct |
0 ms |
356 KB |
Output is correct |
| 9 |
Correct |
283 ms |
55744 KB |
Output is correct |
| 10 |
Execution timed out |
1066 ms |
432936 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
356 KB |
Output is correct |
| 2 |
Correct |
0 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
356 KB |
Output is correct |
| 7 |
Correct |
0 ms |
440 KB |
Output is correct |
| 8 |
Correct |
0 ms |
356 KB |
Output is correct |
| 9 |
Correct |
283 ms |
55744 KB |
Output is correct |
| 10 |
Execution timed out |
1066 ms |
432936 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
356 KB |
Output is correct |
| 2 |
Correct |
0 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
356 KB |
Output is correct |
| 6 |
Correct |
0 ms |
356 KB |
Output is correct |
| 7 |
Correct |
0 ms |
440 KB |
Output is correct |
| 8 |
Correct |
0 ms |
356 KB |
Output is correct |
| 9 |
Correct |
283 ms |
55744 KB |
Output is correct |
| 10 |
Execution timed out |
1066 ms |
432936 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
838 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
910 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
