| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 638183 |
2022-09-04T20:49:25 Z |
blue |
Catfish Farm (IOI22_fish) |
C++17 |
|
49 ms |
28716 KB |
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())
const int lg = 18;
void selfmax(ll& a, ll b)
{
a = max(a, b);
}
const int maxN = 100'000;
vpll fish[1 + maxN];
vll fishpref[1 + maxN];
vll tot(1 + maxN, 0);
int maxind(int i, int h)
{
//return max ind of col i so that corresponding height is <= h
int b = -1;
for(int e = lg; e >= 0; e--)
{
if(b + (1<<e) < sz(fish[i]) && fish[i][b + (1<<e)].first <= h)
b += (1<<e);
}
return b;
}
ll htwt(int i, int h)
{
int j = maxind(i, h);
if(j == -1)
return 0;
else
return fishpref[i][j];
}
ll invhtwt(int i, int h)
{
return tot[i] - htwt(i, h-1);
}
ll max_weights(int N, int M, vi X, vi Y, vi W)
{
int xmx = 0;
for(int j = 0; j < M; j++)
{
X[j]++;
xmx = max(xmx, X[j]);
Y[j]++;
}
vpll fish[1+N];
vll fishpref[1+N];
vpii fishbyY[1+N];
for(int j = 0; j < M; j++)
{
// fish[X[j]].push_back({Y[j], W[j]});
fishbyY[Y[j]].push_back({X[j], W[j]});
tot[X[j]] += W[j];
}
for(int y = 0; y <= N; y++)
for(pii z : fishbyY[y])
fish[z.first].push_back({y, z.second});
for(int r = 1; r <= xmx; r++)
{
fish[r].push_back({N+1, 0});
// sort(fish[r].begin(), fish[r].end());
if(fish[r][0].first != 1)
{
fish[r].insert(fish[r].begin(), {1, 0});
}
fishpref[r] = vll(sz(fish[r]));
for(int i = 0; i < sz(fishpref[r]); i++)
{
fishpref[r][i] = (i == 0 ? 0 : fishpref[r][i-1]) + fish[r][i].second;
}
}
fish[0] = vpll{{0, 0}};
fishpref[0] = vll{0};
vvll inc(1+N), dec(1+N);
vvll incpref(1+N), decpref(1+N); //pref inc dec mx
inc[0] = dec[0] = vll{0};
// cerr << "done\n";
for(int r = 1; r <= xmx; r++)
{
incpref[r-1] = inc[r-1];
decpref[r-1] = dec[r-1];
for(int i = 1; i < sz(fish[r-1]); i++)
{
incpref[r-1][i] = max(incpref[r-1][i-1], inc[r-1][i]);
decpref[r-1][i] = max(decpref[r-1][i-1], dec[r-1][i]);
}
inc[r] = dec[r] = vll(sz(fish[r]), 0);
vll Csuff;
if(r >= 2)
{
Csuff = vll(sz(fish[r-2]));
int pi = sz(fish[r-1])-1;
ll pwt = tot[r-1];
for(int j = sz(fish[r-2])-1; j >= 0; j--)
{
while(pi >= 0 && fish[r-1][pi].first > fish[r-2][j].first - 1)
{
pwt -= fish[r-1][pi].second;
pi--;
}
// Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + htwt(r-1, fish[r-2][j].first - 1);
Csuff[j] = max(inc[r-2][j], dec[r-2][j]) + pwt;
if(j+1 < sz(fish[r-2]))
selfmax(Csuff[j], Csuff[j+1]);
}
}
ll Dmx = 0;
ll Did = -1;
int ppi = -1;
int qi = -1;
ll qwt = 0;
for(int i = 0; i < sz(fish[r]); i++)
{
ll basic = 0;
ll Bcatch = 0;
int Bk = -1;
while(qi+1 < sz(fish[r-1]) && fish[r-1][qi+1].first <= fish[r][i].first - 1)
{
qi++;
qwt += fish[r-1][qi].second;
}
// ll prevpwt = htwt(r-1, fish[r][i].first - 1);
// cerr << prevpwt << " " << qwt << '\n';
// assert(prevpwt == qwt);
ll prevpwt = qwt;
ll constD = -(tot[r-1] - prevpwt) + tot[r-1];
if(r >= 2)
{
//A
selfmax(basic, max(inc[r-2][0], dec[r-2][0]) + prevpwt);
while(ppi+1 < sz(fish[r-2]) && fish[r-2][ppi+1].first <= fish[r][i].first)
ppi++;
int ploci = ppi;
//B
/*for(int j = 0; j <= ploci; j++)
{
// cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
ll medcatch = 0;
for(int k = 0; k < sz(fish[r-1]); k++)
if(fish[r-1][k].first <= fish[r][i].first - 1)
medcatch += fish[r-1][k].second;
selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
}*/
while(Bk+1 < sz(fish[r-1]) && fish[r-1][Bk+1].first <= fish[r][i].first - 1)
{
Bk++;
Bcatch += fish[r-1][Bk].second;
}
selfmax(basic, Bcatch + max(incpref[r-2][ploci], decpref[r-2][ploci]));
// for(int j = 0; j <= ploci; j++)
// {
// // cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
// // selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + Bcatch);
// selfmax(basic, )
// }
//C
// for(int j = sz(fish[r-2])-1; j > ploci; j--)
// {
// // cerr << "j = " << j << " out of (exc) " << sz(fish[r-2]) << '\n';
// ll medcatch = 0;
// for(int k = 0; k < sz(fish[r-1]); k++)
// if(fish[r-1][k].first <= fish[r-2][j].first - 1)
// medcatch += fish[r-1][k].second;
// selfmax(basic, max(inc[r-2][j], dec[r-2][j]) + medcatch);
// }
if(ploci+1 < sz(fish[r-2]))
{
// cerr << ploci << " : " << sz(fish[r-2]) << '\n';
selfmax(basic, Csuff[ploci+1]);
}
}
selfmax(inc[r][i], basic);
selfmax(dec[r][i], basic);
//type D transition
while(Did+1 < sz(fish[r-1]) && fish[r-1][Did+1].first <= fish[r][i].first)
{
Did++;
Dmx = max(Dmx, inc[r-1][Did] - (Did >= 1 ? fishpref[r-1][Did-1] : 0));
}
// for(int j = 0; j < sz(fish[r-1]) && fish[r-1][j].first <= fish[r][i].first; j++)
// {
// // cerr << "j = " << j << " , " << fish[r-1][j].first-1 << '\n';
// // ll ext = 0;
// // cerr << "case 1\n";
// // for(int k = j; k < sz(fish[r-1]); k++)
// // {
// // if(fish[r-1][k].first <= fish[r][i].first - 1)
// // ext += fish[r-1][k].second;
// // }
// // if(j >= 1)
// // ext -= fishpref[r-1][j-1];
// // ll ext = -invhtwt(r-1, fish[r][i].first);
// selfmax(inc[r][i], inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + constD);
// selfmax(dec[r][i], inc[r-1][j] - (j >= 1 ? fishpref[r-1][j-1] : 0) + constD);
// }
selfmax(inc[r][i], Dmx + constD);
selfmax(dec[r][i], Dmx + constD);
}
int j = sz(fish[r-1]);
ll bestval = -1'000'000'000'000'000'000LL;
int ri = sz(fish[r]);
ll rwt = 0;
for(int i = sz(fish[r])-1; i >= 0; i--)
{
while(j-1 >= 0 && fish[r-1][j-1].first > fish[r][i].first)
{
j--;
while(ri-1 >= 0 && fish[r][ri-1].first >= fish[r-1][j].first)
{
ri--;
rwt += fish[r][ri].second;
}
bestval = max(bestval, dec[r-1][j] + tot[r] - rwt);
}
selfmax(dec[r][i], bestval - (i >= 1 ? fishpref[r][i-1] : 0));
}
}
ll res = 0;
for(vll x : inc)
for(ll y : x)
res = max(res, y);
for(vll x : dec)
for(ll y : x)
res = max(res, y);
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
28716 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
22228 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
22228 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
28716 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
