oj.uz

Submission #832927

# Submission time Handle Problem Language Result Execution time Memory
832927 2023-08-21T16:44:49 Z Rafi22 Catfish Farm (IOI22_fish) C++17
9 / 100
 465 ms 159064 KB 
#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=100007;

set<int>S[N];
vector<int>points[N];

vector<ll>DP[2][N];
vector<ll>L[N];
vector<ll>R[N];
vector<ll>M[N];


vector<pair<int,int>>V[N];
     
ll max_weights(int n,int m,vector<int>X,vector<int>Y,vector<int>W)
{
	for(int i=0;i<m;i++)
	{
		X[i]++;
		Y[i]++;
		S[X[i]].insert(Y[i]-1);
		S[X[i]-1].insert(Y[i]);
		S[X[i]+1].insert(Y[i]);
		V[X[i]].pb({Y[i],W[i]});
	}
	for(int i=1;i<=n;i++)
	{
		S[i].insert(0);
		sort(all(V[i]));
		for(auto x:S[i]) points[i].pb(x);
		DP[0][i].resize(sz(points[i]),0);
		DP[1][i].resize(sz(points[i]),0);
		L[i].resize(sz(points[i]),0);
		R[i].resize(sz(points[i]),0);
		M[i].resize(sz(points[i]),0);
	}
	for(int i=1;i<=n;i++)
	{
		vector<pair<int,ll>>P;
		for(auto [y,c]:V[i-1]) P.pb({y,-c});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		ll sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) L[i][c]=sum;
			else sum+=-c;
		}
		P.clear();
		for(auto [y,c]:V[i+1]) P.pb({y,-c});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) R[i][c]=sum;
			else sum+=-c;
		}
		P.clear();
		for(auto [y,c]:V[i]) P.pb({y,-c});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) M[i][c]=sum;
			else sum+=-c;
		}
	}
	for(auto x:points[1]) DP[1][1][x]=-infl;
	ll ans=0;
	for(int i=2;i<=n;i++)
	{
		vector<pair<int,int>>P;
		for(int j=0;j<sz(points[i-2]);j++) P.pb({points[i-2][j],-j-1});
		//for(auto y:points[i-2]) P.pb({y,0});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		//for(auto y:points[i]) P.pb({y,1});
		sort(all(P));
		ll mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max({mx,DP[0][i-2][-c-1],DP[1][i-2][-c-1]});
			else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,max(DP[0][i-2][-c-1],DP[1][i-2][-c-1])+R[i-2][-c-1]);
			else DP[0][i][c]=max(DP[0][i][c],mx);
		}
		P.clear();
		for(int j=0;j<sz(points[i-1]);j++) P.pb({points[i-1][j],-j-1});
		//for(auto y:points[i-1]) P.pb({y,0});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		//for(auto y:points[i]) P.pb({y,1});
		sort(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,DP[0][i-1][-c-1]-M[i-1][-c-1]);
			else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,max(DP[0][i-1][-c-1],DP[1][i-1][-c-1])+R[i-1][-c-1]);
			else DP[1][i][c]=max(DP[1][i][c],mx-M[i][c]);
		}
		for(int j=0;j<sz(points[i]);j++) ans=max({ans,DP[0][i][j],DP[1][i][j]});
	}
	return ans;
}
  /* 
int main()
{
	cout<<max_weights(5, 4,{0, 1, 4, 3},{2, 1, 4, 3},{5, 2, 1, 3})<<endl;
	return 0;
}*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 131384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Runtime error 465 ms 150752 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 44896 KB Output is correct
2 Correct 65 ms 44904 KB Output is correct
3 Correct 110 ms 48248 KB Output is correct
4 Correct 101 ms 48812 KB Output is correct
5 Correct 177 ms 55040 KB Output is correct
6 Correct 174 ms 54972 KB Output is correct
7 Correct 178 ms 54988 KB Output is correct
8 Correct 207 ms 54976 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 11 ms 21348 KB Output is correct
3 Correct 12 ms 21332 KB Output is correct
4 Correct 13 ms 21356 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 11 ms 21344 KB Output is correct
7 Correct 11 ms 21332 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21440 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Runtime error 33 ms 43596 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 11 ms 21348 KB Output is correct
3 Correct 12 ms 21332 KB Output is correct
4 Correct 13 ms 21356 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 11 ms 21344 KB Output is correct
7 Correct 11 ms 21332 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21440 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Runtime error 33 ms 43596 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21332 KB Output is correct
2 Correct 11 ms 21348 KB Output is correct
3 Correct 12 ms 21332 KB Output is correct
4 Correct 13 ms 21356 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 11 ms 21344 KB Output is correct
7 Correct 11 ms 21332 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21440 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Runtime error 33 ms 43596 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 44896 KB Output is correct
2 Correct 65 ms 44904 KB Output is correct
3 Correct 110 ms 48248 KB Output is correct
4 Correct 101 ms 48812 KB Output is correct
5 Correct 177 ms 55040 KB Output is correct
6 Correct 174 ms 54972 KB Output is correct
7 Correct 178 ms 54988 KB Output is correct
8 Correct 207 ms 54976 KB Output is correct
9 Correct 197 ms 59784 KB Output is correct
10 Correct 139 ms 41728 KB Output is correct
11 Correct 352 ms 62052 KB Output is correct
12 Correct 11 ms 21332 KB Output is correct
13 Correct 12 ms 21332 KB Output is correct
14 Correct 11 ms 21332 KB Output is correct
15 Correct 11 ms 21404 KB Output is correct
16 Correct 11 ms 21332 KB Output is correct
17 Correct 11 ms 21392 KB Output is correct
18 Correct 61 ms 44904 KB Output is correct
19 Correct 60 ms 44784 KB Output is correct
20 Correct 61 ms 44904 KB Output is correct
21 Correct 60 ms 44808 KB Output is correct
22 Correct 268 ms 70028 KB Output is correct
23 Correct 384 ms 81228 KB Output is correct
24 Runtime error 404 ms 159064 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 131384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -