| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 753666 |
2023-06-05T16:20:41 Z |
midi |
Catfish Farm (IOI22_fish) |
C++17 |
|
1000 ms |
2097152 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vcll;
typedef pair<ll, ll> prll;
#define f0r(i, a, n) for (i = a; i < n; i++)
#define f1r(i, a, n) for (i = a; i <= n; i++)
#define r0f(i, n, a) for (i = n; i > a; i--)
#define r1f(i, n, a) for (i = n; i >= a; i--)
#define mxN 100000
#define mxM 300000
#define rest_input int n, int m, vector<int> x, vector<int> y, vector<int> w
#define throw_input n, m, x, y, w
#define allocate(type, size) (type *)malloc((size) * sizeof(type))
ll n, m;
ll **grid;
ll **psa;
void build_grid(rest_input)
{
grid = allocate(ll *, n + 10);
ll i, j;
f0r(i, 0, n) grid[i] = allocate(ll, n + 10);
f0r(i, 0, n) f0r(j, 0, n) grid[i][j] = 0;
f0r(i, 0, m)
grid[x[i]][y[i]] = w[i];
}
void build_psa(ll n)
{
psa = allocate(ll *, n + 10);
psa++;
ll i, j;
f0r(i, -1, n) psa[i] = allocate(ll, n + 10);
f0r(i, -1, n) psa[i]++;
f0r(j, -1, n) psa[-1][j] = 0;
f0r(i, 0, n)
{
ll run_max = 0;
// printf("at i: %lli\n", i);
f0r(j, -1, n)
{
// printf("on j: %lli : %lli\n", j, run_max);
psa[i][j] = run_max;
run_max += grid[i][j + 1];
}
}
}
ll C(ll i, ll j3, ll j2, ll j)
{
ll j4 = max(j3, j2);
ll sum = 0;
if (j < j2) sum += psa[i][j2] - psa[i][j];
if (j > j4) sum += psa[i - 1][j] - psa[i - 1][j4];
return sum;
}
ll ***memoi;
// bool ***memo_bool;
void init_memoi(ll n)
{
memoi = allocate(ll **, n + 10);
// memoi++;
// memo_bool = allocate(bool **, n + 10);
ll i, j;
f0r(i, -1, n + 10)
{
memoi[i] = allocate(ll *, n + 10);
memoi[i]++;
}
// f0r(i, 0, n + 10) memo_bool[i] = allocate(bool *, n + 10);
f0r(i, -1, n + 10) f0r(j, -1, n + 10)
{
memoi[i][j] = allocate(ll, n + 10);
memoi[i][j]++;
}
// f0r(i, 0, n + 10) f0r(j, 0, n + 10) memo_bool[i][j] = allocate(bool, n + 10);
ll k;
// f0r(i, 0, n + 10) f0r(j, 0, n + 10) f0r(k, 0, n + 10) memo_bool[i][j][k] = 0;
f0r(i, 0, n) f0r(j, -1, n) f0r(k, -1, n) memoi[i][j][k] = -1;
}
ll call_count = 0;
ll subcall_count = 0;
ll memo_count = 0;
ll zero_count = 0;
ll reduct_count = 0;
ll notred_count = 0;
ll dp(ll i, ll j2, ll j3, ll n)
{
call_count++;
if (i == n) return 0;
if (j3 < j2) j3 = j2;
ll &t = memoi[i][j2][j3];
if (t != -1) return t;
ll maximum = -1;
ll j;
f0r(j, -1, n) // incl.
{
ll v = dp(i + 1, j, j2, n) + C(i, j3, j2, j);
if (maximum < v) maximum = v;
}
return (t = maximum);
}
int64_t max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
build_grid(throw_input);
build_psa(n);
init_memoi(n);
ll ans = dp(0, -1, n - 1, n);
// printf("n: %lli\n", (ll)n);
return ans;
}
/*
int main()
{
int n = 5;
cin >> n;
int m = 4;
vcll x = {0, 1, 4, 3};
vcll y = {2, 1, 4, 3};
vcll w = {5, 2, 1, 3};
// vcll x = {0, 1};
// vcll y = {1, 0};
// vcll w = {2, 3};
m = x.size();
printf("real: %lli\n", (long long)max_weights(n, m, x, y, w));
printf("call count: %lli\n", call_count);
printf("subcall count: %lli\n", subcall_count);
printf("memo count: %lli\n", memo_count);
printf("zero count: %lli\n", zero_count);
printf("reduct count: %lli\n", reduct_count);
printf("notred count: %lli\n", notred_count);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
908 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
937 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Execution timed out |
1082 ms |
33748 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Execution timed out |
1082 ms |
33748 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Execution timed out |
1082 ms |
33748 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
937 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1173 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
