oj.uz

Submission #832904

# Submission time Handle Problem Language Result Execution time Memory
832904 2023-08-21T16:30:38 Z Rafi22 Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 242208 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>points[N];
unordered_map<int,ll>DP[2][N];
unordered_map<int,ll>L[N];
unordered_map<int,ll>R[N];
unordered_map<int,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]++;
		points[X[i]].insert(Y[i]-1);
		points[X[i]-1].insert(Y[i]);
		points[X[i]+1].insert(Y[i]);
		V[X[i]].pb({Y[i],W[i]});
	}
	for(int i=1;i<=n;i++)
	{
		points[i].insert(0);
		sort(all(V[i]));
	}
	for(int i=1;i<=n;i++)
	{
		vector<pair<int,int>>P;
		for(auto [y,c]:V[i-1]) P.pb({y,c});
		for(auto y:points[i]) P.pb({y,inf});
		sort(all(P));
		ll sum=0;
		for(auto [y,c]:P)
		{
			if(c==inf) L[i][y]=sum;
			else sum+=c;
		}
		P.clear();
		for(auto [y,c]:V[i+1]) P.pb({y,c});
		for(auto y:points[i]) P.pb({y,infl});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c==inf) R[i][y]=sum;
			else sum+=c;
		}
		P.clear();
		for(auto [y,c]:V[i]) P.pb({y,c});
		for(auto y:points[i]) P.pb({y,inf});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c==inf) M[i][y]=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(auto y:points[i-2]) P.pb({y,0});
		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][y],DP[1][i-2][y]});
			else DP[0][i][y]=max(DP[0][i][y],mx+L[i][y]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c==0) mx=max(mx,max(DP[0][i-2][y],DP[1][i-2][y])+R[i-2][y]);
			else DP[0][i][y]=max(DP[0][i][y],mx);
		}
		P.clear();
		for(auto y:points[i-1]) P.pb({y,0});
		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][y]-M[i-1][y]);
			else DP[0][i][y]=max(DP[0][i][y],mx+L[i][y]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c==0) mx=max(mx,max(DP[0][i-1][y],DP[1][i-1][y])+R[i-1][y]);
			else DP[1][i][y]=max(DP[1][i][y],mx-M[i][y]);
		}
		
		for(auto y:points[i]) ans=max({ans,DP[0][i][y],DP[1][i][y]});
	}
	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 Correct 494 ms 157776 KB Output is correct
2 Correct 631 ms 185320 KB Output is correct
3 Correct 138 ms 109756 KB Output is correct
4 Correct 140 ms 109876 KB Output is correct
5 Execution timed out 1096 ms 242208 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34740 KB Output is correct
2 Correct 754 ms 190396 KB Output is correct
3 Correct 933 ms 219124 KB Output is correct
4 Correct 501 ms 159080 KB Output is correct
5 Correct 622 ms 187116 KB Output is correct
6 Incorrect 19 ms 34644 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 109824 KB Output is correct
2 Incorrect 136 ms 109756 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34644 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Incorrect 18 ms 34752 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34644 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Incorrect 18 ms 34752 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 34644 KB Output is correct
2 Correct 21 ms 34760 KB Output is correct
3 Incorrect 18 ms 34752 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 109824 KB Output is correct
2 Incorrect 136 ms 109756 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 157776 KB Output is correct
2 Correct 631 ms 185320 KB Output is correct
3 Correct 138 ms 109756 KB Output is correct
4 Correct 140 ms 109876 KB Output is correct
5 Execution timed out 1096 ms 242208 KB Time limit exceeded
6 Halted 0 ms 0 KB -