| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1023941 |
2024-07-15T09:51:08 Z |
Otalp |
Catfish Farm (IOI22_fish) |
C++17 |
|
912 ms |
200576 KB |
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
const int MAXN = 500100;
int n, w[MAXN], m;
pii a[MAXN];
namespace B{
map<ll, ll> d[200100];
map<ll, ll> dp[200100];
map<ll, ll> pref[200100];
map<ll, ll> ddp[200100];
vector<ll> pos[200100];
ll suf[200100];
ll solve(){
for(ll i=1; i<=m; i++){
d[a[i].ff][a[i].ss] += w[i];
pos[a[i].ff].pb(a[i].ss);
}
d[0][0] = 1;
pos[0].pb(0);
for(int i=0; i<=n; i++){
d[i][n] = 0;
pos[i].pb(n);
}
for(ll i=1; i<=n; i++){
sort(pos[i].begin(), pos[i].end());
}
for(ll i=1; i<=n; i++){
dp[0][i] = -1e18;
ddp[0][i] = -1e18;
}
dp[0][0] = 0;
ddp[0][0] = 0;
for(ll i=1; i<=n; i++){
//cout<<"_____________________\n";
//cout<<i<<'\n';
vector<ll> alpos;
for(auto h: pos[i-1]) alpos.pb(h);
for(auto h: pos[i+1]) alpos.pb(h);
sort(alpos.begin(), alpos.end());
for(ll h: pos[i]){
ll j = h;
pref[i][j] = pref[i][j - 1] + d[i][j];
}
vector<ll> dpos;
for(auto h: dp[i-1]){
dpos.pb(h.ff);
}
ll mx = -1e18;
ll ls = pos[i].size()-1;
for(ll h = dpos.size()-1; h>=0; h--){
ll j = dpos[h];
while(ls > 0 and pos[i][ls] > j) ls--;
mx = max(mx, dp[i-1][j] + pref[i][j]);
suf[j] = mx;
}
ll pddp = -1e18, pdp = -1e18;
mx = -1e18;
for(ll h = dpos.size()-1; h>=0; h--){
ll j = dpos[h];
mx = max(mx, dp[i-1][j]);
}
ll pls=-1, dpls=-1;
ls = -1;
ll lls = -1;
for(ll j: alpos){
//cout<<j<<' ';
while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
ls += 1;
while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
pdp = max(pdp, ddp[i-1][dpos[ls]]-pref[i-1][pos[i-1][lls]]);
}
while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
ddp[i][j] = mx;
dp[i][j] = 0;
//if(dpls < 0){
// cout<<"asdas\n";
// cout<<j<<'\n';
// cout<<dpls+1<<'\n';
// continue;
//}
ddp[i][j] = max(ddp[i][j], pdp + pref[i-1][pos[i-1][dpls]]);
dp[i][j] = ddp[i][j];
if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
else dp[i][j] = max(dp[i][j], suf[dpos[ls]]-pref[i][pos[i][pls]]);
dp[i][j] = max(dp[i][j], pdp+pref[i-1][pos[i-1][dpls]]);
}
//cout<<'\n';
}
//for(ll i=1; i<=n; i++){
// for(ll j=0; j<=n; j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<'\n';
//}
ll ans = 0;
for(ll i=0; i<=n; i++) ans = max(ans, dp[n][i]);
return ans;
}
}
long long 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++){
a[i] = {X[i-1]+1, Y[i-1]+1};
}
for(int i=1; i<=m; i++){
w[i] = W[i-1];
}
for(int i=1; i<=n; i++){
a[i + m] = {i, 0};
w[i+m] = 0;
}
m += n;
return B::solve();
}
Compilation message
fish.cpp: In function 'long long int B::solve()':
fish.cpp:75:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
| ~~~~~~~^~~~~~~~~~~~~
fish.cpp:77:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
| ~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:80:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
| ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:81:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:92:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
92 | if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
| ~~~~~~~~~~~~^~~~~~~~
fish.cpp:64:16: warning: unused variable 'pddp' [-Wunused-variable]
64 | ll pddp = -1e18, pdp = -1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
151272 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
42588 KB |
Output is correct |
| 2 |
Incorrect |
912 ms |
192288 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '84649862111' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
135336 KB |
Output is correct |
| 2 |
Correct |
268 ms |
135332 KB |
Output is correct |
| 3 |
Correct |
296 ms |
145784 KB |
Output is correct |
| 4 |
Correct |
309 ms |
148864 KB |
Output is correct |
| 5 |
Correct |
363 ms |
170172 KB |
Output is correct |
| 6 |
Correct |
401 ms |
169696 KB |
Output is correct |
| 7 |
Correct |
355 ms |
170168 KB |
Output is correct |
| 8 |
Correct |
345 ms |
170116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
42588 KB |
Output is correct |
| 2 |
Correct |
19 ms |
42536 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
42588 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
42588 KB |
Output is correct |
| 2 |
Correct |
19 ms |
42536 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
42588 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
42588 KB |
Output is correct |
| 2 |
Correct |
19 ms |
42536 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
42588 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
135336 KB |
Output is correct |
| 2 |
Correct |
268 ms |
135332 KB |
Output is correct |
| 3 |
Correct |
296 ms |
145784 KB |
Output is correct |
| 4 |
Correct |
309 ms |
148864 KB |
Output is correct |
| 5 |
Correct |
363 ms |
170172 KB |
Output is correct |
| 6 |
Correct |
401 ms |
169696 KB |
Output is correct |
| 7 |
Correct |
355 ms |
170168 KB |
Output is correct |
| 8 |
Correct |
345 ms |
170116 KB |
Output is correct |
| 9 |
Correct |
426 ms |
195068 KB |
Output is correct |
| 10 |
Correct |
260 ms |
121708 KB |
Output is correct |
| 11 |
Correct |
496 ms |
200576 KB |
Output is correct |
| 12 |
Incorrect |
19 ms |
42636 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
151272 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '36638591909' |
| 2 |
Halted |
0 ms |
0 KB |
- |
