#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
struct fish {
ll x, y, w;
};
ll max_weights(int N, int M, vi X, vi Y, vi W) {
typedef vector<fish> vf;
typedef vector<vf> vvf;
vf f;
L(i, 0ll, M) {
f.pb({X[i], Y[i], W[i]});
}
sort(f.begin(), f.end(), [](const fish& f1, const fish& f2) {return f1.y < f2.y;});
vvf fax;
vvll dpinc;
vvll dpdec;
vvll psum;
L(i, 0ll, N) {
vf faxr(1ll, {i, 0ll, 0ll});
vll dpincr(1ll, 0ll);
vll dpdecr(1ll, 0ll);
vll psumr(N + 1ll, 0ll);
fax.pb(faxr);
dpinc.pb(dpincr);
dpdec.pb(dpdecr);
psum.pb(psumr);
}
L(i, 0ll, M) {
assert(f[i].x < N);
assert(f[i].y + 1ll <= N);
fax[f[i].x].pb(f[i]);
dpinc[f[i].x].pb(0ll);
dpdec[f[i].x].pb(0ll);
// cout << "Anya likes peanuts, Anya hates carrots" << endl;
psum[f[i].x][f[i].y + 1ll] += f[i].w; // += because we have multiple fish per cell
}
// Accumulating sums
L(i, 0ll, N) {
L(j, 1ll, N + 1ll) {
psum[i][j] += psum[i][j - 1ll];
}
}
// ! CAREFUL: you're adding another value
L(i, 0ll, N) {
fax[i].pb({i, N, 0ll});
dpinc[i].pb(0ll);
dpdec[i].pb(0ll);
}
L(i, 1ll, N) {
// Increasing first
const vf& fax1 = fax[i], fax2 = fax[i - 1ll], fax3 = fax[max(i - 2ll, 0ll)];
ll f1s = fax1.size(), f2s = fax2.size(), f3s = fax3.size();
L(j, 0ll, f1s) {
L(k, 0ll, f2s) {
if(fax1[j].y < fax2[k].y) continue; // Decreasing, skip
dpinc[i][j] = max(dpinc[i][j], dpinc[i - 1ll][k] + psum[i - 1ll][fax1[j].y] - psum[i - 1ll][fax2[k].y]);
if(fax2[k].y == 0ll && i > 1ll) {
L(l, 0ll, f3s) {
ll max_y = max(fax1[j].y, fax3[l].y);
dpinc[i][j] = max(dpinc[i][j], dpdec[i - 2ll][l] + psum[i - 1ll][max_y]);
}
}
}
}
// Then decreasing
L(j, 0ll, f1s) {
L(k, 0ll, f2s) {
if(fax1[j].y > fax2[k].y) continue; // Increasing, skip
dpdec[i][j] = max(dpdec[i][j], max(dpinc[i - 1ll][k], dpdec[i - 1ll][k]) + psum[i][fax2[k].y] - psum[i][fax1[j].y]);
}
}
}
// cout << "Y" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << fax1[j].y << " ";
// }
// cout << "\n";
// }
// cout << "DPINC" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << dpinc[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "DPDEC" << endl;
// L(i, 0ll, N) {
// const vf& fax1 = fax[i];
// ll f1s = fax1.size();
// L(j, 0ll, f1s) {
// cout << dpdec[i][j] << " ";
// }
// cout << "\n";
// }
// Final casework for the final answer (do this on the last column)
ll ans = 0ll;
const vf& lastcol = fax[N - 1ll];
ll lastcols = lastcol.size();
L(i, 0ll, lastcols) {
ans = max(ans, max(dpdec[N - 1ll][i], dpinc[N - 1ll][i]));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
886 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
809 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
750 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 |
1 ms |
604 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243' |
| 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 |
1 ms |
604 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243' |
| 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 |
1 ms |
604 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
750 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
886 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
