oj.uz

Submission #826722

# Submission time Handle Problem Language Result Execution time Memory
826722 2023-08-15T22:58:10 Z arnold518 Catfish Farm (IOI22_fish) C++17
12 / 100
 163 ms 33152 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N, M;
vector<pii> V[MAXN+10];
vector<ll> dp1[MAXN+10], dp2[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	void init() { for(int i=1; i<=N; i++) tree[i]=-INF; }
	void update(int i, ll k) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], k); }
	ll query(int i) { ll ret=-INF; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
}bit1, bit2;

ll max_weights(int _N, int _M, vector<int> _X, vector<int> _Y, vector<int> _W)
{
	N=_N; M=_M;
	for(int i=0; i<M; i++)
	{
		int x=_X[i]+1, y=_Y[i]+1, w=_W[i];
		V[x].push_back({y, w});
	}
	for(int i=0; i<=N+1; i++)
	{
		sort(V[i].begin(), V[i].end());
		if(V[i].empty() || V[i][0].first!=1) V[i].push_back({1, 0});
		if(V[i].back().first!=N) V[i].push_back({N, 0});
		sort(V[i].begin(), V[i].end());

		dp1[i]=vector<ll>(V[i].size(), -INF);
		dp2[i]=vector<ll>(V[i].size(), -INF);
	}

	
	bit1.init(); bit2.init();
	dp2[0][0]=0; dp1[0][dp1[0].size()-1]=0;
	ll p=-INF, q=-INF, ans=0;
	for(int i=0; i<=N; i++)
	{
		int t=V[i].size();
		if(i-1>=0) p=max(p, dp2[i-1][0]);
		if(i-2>=0) q=max(q, dp1[i-2].back());

		dp1[i][0]=max(dp1[i][0], p+V[i][0].second);
		if(i-2>=0) dp1[i][0]=max(dp1[i][0], dp1[i-2].back()+V[i][0].second);
		dp2[i][t-1]=max(dp2[i][t-1], q+V[i][t-1].second);
		for(int j=0; j<t; j++)
		{
			auto [y, w] = V[i][j];
			dp1[i][j]=max(dp1[i][j], bit1.query(y-1)+w);
			bit1.update(y, dp1[i][j]);
		}
		for(int j=t-1; j>=0; j--)
		{
			auto [y, w] = V[i][j];
			dp2[i][j]=max(dp2[i][j], bit2.query(N-y)+w);
			bit2.update(N-y+1, dp2[i][j]);
		}

		ans=max(ans, dp2[i][0]);
		// for(auto it : dp1[i]) printf("%lld ", it); printf("\n");
		// for(auto it : dp2[i]) printf("%lld ", it); printf("\n");
		// printf("\n");
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20960 KB Output is correct
2 Correct 63 ms 23012 KB Output is correct
3 Correct 28 ms 18308 KB Output is correct
4 Correct 27 ms 18300 KB Output is correct
5 Correct 142 ms 32344 KB Output is correct
6 Correct 163 ms 33152 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7252 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18288 KB Output is correct
2 Correct 29 ms 18284 KB Output is correct
3 Correct 42 ms 18416 KB Output is correct
4 Correct 42 ms 19164 KB Output is correct
5 Correct 52 ms 20652 KB Output is correct
6 Correct 50 ms 21572 KB Output is correct
7 Correct 56 ms 22092 KB Output is correct
8 Correct 54 ms 22208 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7352 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7352 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7352 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18288 KB Output is correct
2 Correct 29 ms 18284 KB Output is correct
3 Correct 42 ms 18416 KB Output is correct
4 Correct 42 ms 19164 KB Output is correct
5 Correct 52 ms 20652 KB Output is correct
6 Correct 50 ms 21572 KB Output is correct
7 Correct 56 ms 22092 KB Output is correct
8 Correct 54 ms 22208 KB Output is correct
9 Incorrect 65 ms 23564 KB 1st lines differ - on the 1st token, expected: '99999', found: '99998'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20960 KB Output is correct
2 Correct 63 ms 23012 KB Output is correct
3 Correct 28 ms 18308 KB Output is correct
4 Correct 27 ms 18300 KB Output is correct
5 Correct 142 ms 32344 KB Output is correct
6 Correct 163 ms 33152 KB Output is correct
7 Incorrect 3 ms 7252 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -