| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 627347 | minhcool | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const ll oo = 1e18 + 7, mod = 1e9 + 7;
ll n, m;
ll x[N], y[N], w[N];
ll solve1(){
ll tol = 0;
for(int i = 1; i <= m; i++) tol += w[i];
return tol;
}
map<ii, ll> mp;
ll solve2(){
for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
if(n >= 3){
ll mx = -1, total = 0;
for(int i = 1; i <= n; i++) total += mp[{2, i}];
mx = total;
for(int i = 1; i <= n; i++){
total += (mp[{1, i}] - mp[{2, i}]);
mx = max(mx, total);
}
return mx;
}
else{
return max(mp[{1, 1}] + mp[{1, 2}], mp[{2, 1}] + mp[{2, 2}]);
}
}
ll dp1[N][2][2];
ll solve3(){
//cout << "OK\n";
for(int i = 1; i <= m; i++) mp[{x[i], y[i]}] = w[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++) dp1[i][j][k] = -oo;
}
}
dp1[1][0][0] = dp1[1][1][0] = 0;
for(int i = 2; i <= (n + 1); i++){
for(int j = 0; j < 2; j++){
if(i == (n + 1) && j) break;
for(int k = 0; k < 2; k++){
for(int h = 0; h < 2; h++){
dp1[i][j][k] = max(dp1[i][j][k], dp1[i - 1][k][h] + mp[{i - 1, 1}] * (!k && (j | h)));
}
//cout << i << " " << j << " " << k << " " << dp1[i][j][k] << "\n";
}
}
}
return max(dp1[n + 1][0][0], dp1[n + 1][0][1]);
}
ll dp2[305][305][305];
ll cell[305][305];
ll solve4_5(){
for(int i = 1; i <= m; i++) cell[x[i]][y[i]] = w[i];
/*
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++) cout << cell[i][j] << " ";
cout << "\n";
}*/
for(int i = 1; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int k = 0; k <= n; k++) dp2[i][j][k] = -oo;
}
}
for(int i = 0; i <= n; i++) dp2[1][i][0] = 0;
//cout << "OK\n";
/*
j >= max(i, k) => j = n, b/c why not?
j <= min(i, k) => j = 0, b/c why not?
i > j >= k => (i, j) = f(i, j) + max(dp[-1][j][0 -> j])
i < j <= k => (i, j) = f(i, j) + max(dp[-1][j][j -> k] + f(j, j -> k))
*/
for(int r = 2; r <= (n + 1); r++){
// j = n
for(int i = 0; i <= n; i++){
for(int k = 0; k <= n; k++){
dp2[r][i][n] = max(dp2[r][i][n], dp2[r - 1][n][k]);
}
}
// j = 0
ll pref = 0;
for(int i = 0; i <= n; i++){
pref += cell[r - 1][i];
ll pref2 = pref;
for(int k = 0; k <= n; k++){
if(k > i) pref2 += cell[r - 1][k];
dp2[r][i][0] = max(dp2[r][i][0], dp2[r - 1][0][k] + pref2);
//cout << i << " " << k << " " << dp2[r - 1][0][k] + pref2 << "\n";
}
}
// i > j >= k
for(int j = 0; j <= n; j++){
ll pref = 0;
for(int k = 0; k < j; k++) pref = max(pref, dp2[r - 1][j][k]);
for(int i = j + 1; i <= n; i++){
pref += cell[r - 1][i];
dp2[r][i][j] = max(dp2[r][i][j], pref);
}
}
for(int j = 0; j <= n; j++){
ll mx = 0, pref = 0;
for(int k = j + 1; k <= n; k++){
pref += cell[r - 1][k];
mx = max(mx, dp2[r - 1][j][k] + pref);
}
for(int i = 0; i < j; i++) dp2[r][i][j] = max(dp2[r][i][j], mx);
}
/*
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++) cout << r << " " << i << " " << j << " " << dp2[r][i][j] << "\n";
}*/
}
ll mx = -1;
for(int i = 0; i <= n; i++) mx = max(mx, dp2[n + 1][0][i]);
return mx;
}
ll dp3[N][11][11];
vector<int> cells[N];
ll solve7(){
for(int i = 1; i <= m; i++){
mp[{x[i], y[i]}] = y[i];
for(int j = max(1LL, x[i] - 1); j <= min(n, x[i] + 1); j++){
cells[j].pb(y[i]);
}
}
for(int i = 1; i <= n; i++){
cells[i].pb(0);
sort(cells[i].begin(), cells[i].end());
cells[i].resize(unique(cells[i].begin(), cells[i].end()) - cells[i].begin());
}
for(int i = 1; i <= n + 1; i++){
for(int j = 0; j <= 6; j++){
for(int k = 0; k <= 6; k++) cells[j][k] =
}
}
for(int i = 0; i <= cells[1].size(); i++) dp3[1][i][0] = 0;
for(int r = 2; r <= (n + 1); r++){
// j = n
for(int i = 0; i <= n; i++){
for(int k = 0; k <= n; k++){
dp2[r][i][n] = max(dp2[r][i][n], dp2[r - 1][n][k]);
}
}
// j = 0
ll pref = 0;
for(int i = 0; i <= n; i++){
pref += cell[r - 1][i];
ll pref2 = pref;
for(int k = 0; k <= n; k++){
if(k > i) pref2 += cell[r - 1][k];
dp2[r][i][0] = max(dp2[r][i][0], dp2[r - 1][0][k] + pref2);
//cout << i << " " << k << " " << dp2[r - 1][0][k] + pref2 << "\n";
}
}
// i > j >= k
for(int j = 0; j <= n; j++){
ll pref = 0;
for(int k = 0; k < j; k++) pref = max(pref, dp2[r - 1][j][k]);
for(int i = j + 1; i <= n; i++){
pref += cell[r - 1][i];
dp2[r][i][j] = max(dp2[r][i][j], pref);
}
}
for(int j = 0; j <= n; j++){
ll mx = 0, pref = 0;
for(int k = j + 1; k <= n; k++){
pref += cell[r - 1][k];
mx = max(mx, dp2[r - 1][j][k] + pref);
}
for(int i = 0; i < j; i++) dp2[r][i][j] = max(dp2[r][i][j], mx);
}
}
}
ll max_weights(int _n, int _m, vector<int> _x, vector<int> _y, vector<int> _w){
n = _n, m = _m;
for(int i = 1; i <= m; i++){
x[i] = _x[i - 1] + 1, y[i] = _y[i - 1] + 1, w[i] = _w[i - 1];
//cout << x[i] << " " << y[i] << " " << w[i] << "\n";
}
bool ck = 1;
for(int i = 1; i <= m; i++) ck &= (x[i] % 2);
if(ck) return solve1();
ck = 1;
for(int i = 1; i <= m; i++) ck &= (x[i] <= 2);
if(ck) return solve2();
ck = 1;
for(int i = 1; i <= m; i++) ck &= (y[i] == 1);
if(ck) return solve3();
ck = (n <= 300);
if(ck) return solve4_5();
return solve7();
//assert(0);
}
/*
void process(){
int n, m;
vector<int> a, b, c;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y, z;
cin >> x >> y >> z;
a.pb(x), b.pb(y), c.pb(z);
}
cout << max_weights(n, m, a, b, c) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
freopen("fish.inp", "r", stdin);
freopen("fish.out", "w", stdout);
//cout << "OK\n";
//return 0;
process();
}*/