#include "fish.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define NN 310
ll grid[NN][NN];
ll n;
ll dp1[NN][NN];
ll noreq(ll, ll); // no request fishies, so len == prev wall.
ll dp2[NN][NN];
ll req(ll, ll);
// previous column did NOT request any right fishies here
// so we simply have a free wall to attach to
ll noreq(ll i, ll len) {
if (i == n) return 0;
auto &DP = dp1[i][len];
if (!~DP) {
DP = noreq(i+1, n); // no restrictions so build big wall.
F(nlen, 0, n+1) DP = max(DP, req(i, nlen)); // basically can set up any wall here before taking right fishes
ll lsum = 0;
F(j, 0, len) lsum += grid[i][j];
DP = max(DP, lsum + noreq(i+1, 0)); // no wall, no requests
F(covering, len, n) {
// not lsum naymore jsut cum sum
lsum += grid[i][covering];
DP = max(DP, lsum + req(i+1, covering + 1));
}
}
return DP;
}
// previous column requested right fishes here;
// so len == min bound on wall (we cannot take anything below len)
ll req(ll i, ll len) {
if (i == n) return len == 0 ? 0 : -1e18; // i should need 0 fishes here
auto &DP = dp2[i][len];
if (!~DP) {
// note that we cannot request any left fishes here.
DP = noreq(i+1, n); // if we don't request ANY fish here, just go up to max
ll sm = 0;
F(covering, len, n) {
sm += grid[i][covering];
DP = max(DP, sm + req(i+1, covering + 1));
}
}
return DP;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
if (N > 300) return -1;
memset(dp1, -1, sizeof dp1);
memset(dp2, -1, sizeof dp2);
n = N;
memset(grid, 0, sizeof grid);
F(i, 0, M) grid[X[i]][Y[i]] = W[i];
return noreq(0, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
4180 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '-1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2460 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2460 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
2460 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '-1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
