#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
vector<vector<pair<int,int>>> fish;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
fish.resize(N);
for(int i = 0; i<M; i++){
fish[X[i]].pb({Y[i],W[i]});
}
for(auto &x: fish){
sort(all(x));
}
vector<vector<long long>> pref(N,vector<long long>(N+1,0));
for(int i = 0; i<N; i++){
int ind = 0;
if(!fish[i].empty() and fish[i][0].f == 0){
pref[i][1] = fish[i][0].s; ind++;
}
for(int j = 1; j<N; j++){
pref[i][j+1] = pref[i][j];
if(ind<sz(fish[i]) and fish[i][ind].f == j){
pref[i][j+1] += fish[i][ind].s;
ind++;
}
}
}
/*for(auto &x: pref){
for(auto &y: x){
cout<<y<<" ";
}
cout<<endl;
}*/
/*
0 : xx
1 : xy
2 : yx
3 : yy
*/
long long dp[N][N+1][N+1]; for(auto &x: dp) for(auto &y: x) for(auto &z: y) z = 0;
vector<long long> mx(N+1); for(auto &x: mx) x = 0;
vector<long long> indx(N+1); for(auto &x: indx) x = 0;
for(int i = 0; i<N+1; i++){
for(int j = 0; j<N+1; j++){
dp[1][i][j] = (max(0LL,pref[0][i]-pref[0][j])) + (max(0LL,pref[1][j] - pref[1][i]));
if(mx[i]<dp[1][i][j]){
mx[i] = dp[1][i][j];
indx[i] = j;
}
}
}
for(int i = 2; i<N; i++){
vector<long long> nmx(N+1,0);
vector<long long> nindx(N+1);
for(int j = 0; j<N+1; j++){
for(int k = 0; k<N+1; k++){
long long temp = mx[k] + max(0LL,pref[i][k]-pref[i][j]) + max(0LL,min(pref[i-1][j]-pref[i-1][indx[k]],pref[i-1][j]-pref[i-1][k]));
dp[i][j][k] = temp;
if(nmx[j] < temp){
nmx[j] = temp;
nindx[j] = k;
}
}
}
mx = nmx;
indx = nindx;
}
long long ans = 0;
for(auto &x: dp[N-1]){
for(auto &y: x){
ans = max(ans,y);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
888 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
865 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
810 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
20 ms |
27308 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '183938242595' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
20 ms |
27308 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '183938242595' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Incorrect |
20 ms |
27308 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '183938242595' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
810 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
888 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
