| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1056529 |
2024-08-13T09:53:56 Z |
pawned |
Catfish Farm (IOI22_fish) |
C++17 |
|
830 ms |
2097152 KB |
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "fish.h"
int MAX_H = 10;
ll max_weights(int N, int M, vector<int> X_g, vector<int> Y_g, vector<int> W_g) {
MAX_H = min(MAX_H, N);
// precompute all range increasing / decreasing
vector<vi> a(N, vi(N, 0));
for (int i = 0; i < M; i++) {
a[X_g[i]][Y_g[i]] += W_g[i];
}
vector<vi> pfs(N, vi(N + 1, 0));
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
pfs[i][j] = pfs[i][j - 1] + a[i][j - 1];
}
}
/* cout<<"a: "<<endl;
for (vi v : a) {
for (int x : v)
cout<<x<<" ";
cout<<endl;
}*/
vector<vector<vi>> inc(N, vector<vi>(N, vi(MAX_H + 1, 0)));
// inc[i][j][k] (i < j): max sum of going up on [i, j]
// only considering [0, k - 1]
vector<vector<vi>> dec(N, vector<vi>(N, vi(MAX_H + 1, 0)));
// dec[i][j][k] (i < j): max sum of going down on [i, j]
// only considering [k, MAX_H - 1]
for (int i = 0; i < N; i++) { // left pos
// compute for [i, i]
inc[i][i][0] = 0;
dec[i][i][MAX_H] = 0;
for (int j = 1; j < MAX_H; j++) {
inc[i][i][j] = inc[i][i][j - 1] + a[i][j - 1];
}
for (int j = MAX_H - 1; j >= 0; j--) {
dec[i][i][j] = dec[i][i][j + 1] + a[i][j];
}
for (int j = i + 1; j < N; j++) { // [i, j], inclusive
for (int k = 0; k <= MAX_H; k++) { // min / max height is k
for (int l = 0; l <= k; l++) { // increasing
// use [l, k-1] for new coln
inc[i][j][k] = max(inc[i][j][k], inc[i][j - 1][l] + (pfs[j][k] - pfs[j][l]));
}
for (int l = k; l <= MAX_H; l++) { // decreasing
// use [k, l-1] for new coln
dec[i][j][k] = max(dec[i][j][k], dec[i][j - 1][l] + (pfs[j][l] - pfs[j][k]));
}
}
}
}
vector<vi> incr(N, vi(N, 0));
vector<vi> decr(N, vi(N, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
incr[i][j] = inc[i][j][MAX_H];
decr[i][j] = dec[i][j][0];
}
}
/* cout<<"incr: "<<endl;
for (vi v : incr) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}
cout<<"decr: "<<endl;
for (vi v : decr) {
for (ll x : v)
cout<<x<<" ";
cout<<endl;
}*/
vector<vi> dp(N, vi(2, 0));
// dp[i][j]: maximum sum until i (exclusive) given last coln type j
// j = 0: increasing ended; j = 1: decreasing ended
// only inc can follow dec without skip; rest all need skip
// can only start w/ inc or blank
// can only end w/ dec or blank
dp[0][0] = incr[0][0];
dp[0][1] = -1e18;
for (int i = 1; i < N; i++) {
// compute dp[i][0]
dp[i][0] = incr[0][i]; // nothing else
for (int j = 0; j < i; j++) { // prev was decr
// start new incr at j+1
dp[i][0] = max(dp[i][0], dp[j][1] + incr[j + 1][i]);
}
for (int j = 1; j < i; j++) { // prev was incr
// need to skip j to start new incr at j+1
dp[i][0] = max(dp[i][0], dp[j - 1][0] + incr[j + 1][i]);
}
// compute dp[i][1]
dp[i][1] = decr[1][i];
for (int j = 1; j < i; j++) { // prev was incr
dp[i][1] = max(dp[i][1], dp[j - 1][0] + decr[j + 1][i]);
}
for (int j = 1; j < i; j++) { // prev was decr
dp[i][1] = max(dp[i][1], dp[j - 1][1] + decr[j + 1][i]);
}
}
/* cout<<"dp: "<<endl;
for (int i = 0; i < N; i++) {
cout<<dp[i][0]<<", "<<dp[i][1]<<endl;
}*/
return max(dp[N - 2][0], dp[N - 1][1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
830 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 |
740 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
679 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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '5050', found: '3030' |
| 5 |
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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '5050', found: '3030' |
| 5 |
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 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '5050', found: '3030' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
679 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
830 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
