QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #506526 | #4561. Catfish Farm | Dan4Life# | 0 | 1ms | 5860kb | C++23 | 1.6kb | 2024-08-05 18:53:02 | 2024-08-05 18:53:03 |
answer
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = (int)1e5+10;
const int mxN2 = (int)3e2+10;
const ll LINF = (ll)2e18;
int n, m;
struct Fish{ int x, y, w; };
vector<Fish> fishes;
ll dp[mxN][10][10];
ll pref[mxN2][mxN2];
int mxY = 9;
ll max_weights(int N, int M, vi _X, vi _Y, vi _W) {
n = N, m = M; mxY=min(mxY,N);
for(int i = 0; i < m; i++)
fishes.pb({_X[i]+1,_Y[i]+1,_W[i]});
sort(all(fishes),[&](Fish a, Fish b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
});
for(int i = 0; i < m; i++){
auto [x,y,w] = fishes[i];
pref[x][y]+=w;
}
for(int i = 0; i <= n; i++)
for(int j = 1; j <= n; j++)
pref[i][j]+=pref[i][j-1];
for(int i = 0; i <= n; i++)
for(int j = 0; j <= mxY; j++)
for(int k = 0; k <= mxY; k++)
dp[i][j][k]=-LINF;
ll ans = 0;
for(int i = 0; i <= mxY; i++){
for(int j = 0; j <= mxY; j++){
if(i>j) dp[2][i][j]=pref[1][i]-pref[1][j];
else if(i<j) dp[2][i][j]=pref[2][j]-pref[2][i];
else dp[2][i][j]=0;
dp[2][i][j]+=pref[3][i];
ans=max(ans, dp[2][i][j]);
}
}
for(int i = 3; i <= n; i++){
for(int j = 0; j <= mxY; j++){
for(int k = 0; k <= mxY; k++){
for(int l = 0; l <= mxY; l++){
int cost = 0;
if(j>max(k,l)) cost = pref[i-1][j]-pref[i-1][max(k,l)];
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l]+cost-pref[i][min(k,j)]);
}
dp[i][j][k] += pref[i+1][j];
ans = max(ans, dp[i][j][k]);
}
}
}
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 90000 80699 0 10792 55091480 0 36762 389250726 0 79267 706445371 0 76952 290301137 0 13444 69711795 0 68980 66221400 0 1695 703252611 0 36628 632571604 0 87676 264578012 0 79496 397448339 0 57929 447544332 0 35453 355374818 0 62449 686423696 0 45614 667165709...
output:
Unauthorized output
result:
Subtask #2:
score: 0
Runtime Error
Test #7:
score: 6
Accepted
time: 0ms
memory: 5856kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 3 2 0 0 1 1 1 1
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 2
result:
ok 3 lines
Test #8:
score: 0
Runtime Error
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 90000 161862 0 56823 293232472 0 28967 124369573 1 8799 138712011 0 87115 743135614 1 56429 262092699 0 61318 597172732 0 39127 477101342 1 44938 277680401 1 79037 997527330 1 88113 13289754 0 29715 35249311 0 50637 709319782 1 20760 845594381 1 80662 6299890...
output:
Unauthorized output
result:
Subtask #3:
score: 0
Runtime Error
Test #20:
score: 0
Runtime Error
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 100000 1 0 0 10082010
output:
Unauthorized output
result:
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 14
Accepted
time: 0ms
memory: 3820kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 4 3 2 2 1 0 0 1 1 1 1
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 3
result:
ok 3 lines
Test #29:
score: 14
Accepted
time: 1ms
memory: 5860kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 8 7 5 5 1 4 4 1 6 6 1 3 3 1 0 0 1 2 2 1 1 1 1
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 7
result:
ok 3 lines
Test #30:
score: 14
Accepted
time: 0ms
memory: 3868kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 3 2 0 0 1 1 1 1
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 2
result:
ok 3 lines
Test #31:
score: 14
Accepted
time: 0ms
memory: 3792kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 3 2 2 0 1 1 1 1
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 2
result:
ok 3 lines
Test #32:
score: 0
Wrong Answer
time: 1ms
memory: 4292kb
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 150 600 79 2 983288470 11 0 322623476 136 0 774411048 24 2 816724362 21 2 719492379 33 3 892309581 47 0 473707335 31 2 781573473 138 2 82986686 75 1 126753954 20 1 54988783 121 1 691958594 20 0 545299878 96 0 637112704 108 1 558914127 74 2 517404335 94 1 7420...
output:
938f2698235a9ff1d1d91e23381b68bec7bed102 OK 203429933902
result:
wrong answer 3rd lines differ - expected: '216624184325', found: '203429933902'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Runtime Error
Test #60:
score: 0
Runtime Error
input:
f785163bfcb92ce6ac387bba5d2f29a0e0f37f19 100000 99999 31026 31026 1 42940 42940 1 69303 69303 1 90350 90350 1 77507 77507 1 87126 87126 1 17988 17988 1 5146 5146 1 63023 63023 1 27776 27776 1 6136 6136 1 82557 82557 1 24904 24904 1 21667 21667 1 67271 67271 1 80294 80294 1 81145 81145 1 47144 47144 ...
output:
Unauthorized output
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
0%