oj.uz

Submission #832953

# Submission time Handle Problem Language Result Execution time Memory
832953 2023-08-21T17:05:45 Z Rafi22 Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 142376 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(int i=0;i<sz(points[1]);i++) DP[1][1][i]=-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(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		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()
{
	int n=100000,m=100000;
	//cin>>n>>m;
	vector<int>X(m),Y(m),C(m);
	for(int i=0;i<m;i++)
	{
		//cin>>X[i]>>Y[i]>>C[i];
		X[i]=rand()%n;
		Y[i]=rand()%n;
		C[i]=rand()%1000000+1;
	}
	cout<<max_weights(n,m,X,Y,C)<<endl;
	return 0;
}*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 70052 KB Output is correct
2 Correct 311 ms 77964 KB Output is correct
3 Correct 60 ms 44884 KB Output is correct
4 Correct 60 ms 44896 KB Output is correct
5 Execution timed out 1091 ms 142376 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21324 KB Output is correct
2 Correct 471 ms 81504 KB Output is correct
3 Correct 624 ms 90208 KB Output is correct
4 Correct 258 ms 70020 KB Output is correct
5 Correct 306 ms 78028 KB Output is correct
6 Correct 11 ms 21332 KB Output is correct
7 Correct 13 ms 21440 KB Output is correct
8 Correct 12 ms 21436 KB Output is correct
9 Correct 12 ms 21332 KB Output is correct
10 Correct 67 ms 44912 KB Output is correct
11 Correct 59 ms 44900 KB Output is correct
12 Correct 314 ms 75120 KB Output is correct
13 Correct 411 ms 84072 KB Output is correct
14 Correct 291 ms 70620 KB Output is correct
15 Correct 241 ms 67948 KB Output is correct
16 Correct 249 ms 70620 KB Output is correct
17 Correct 274 ms 77872 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 44900 KB Output is correct
2 Correct 63 ms 44984 KB Output is correct
3 Correct 109 ms 48136 KB Output is correct
4 Correct 97 ms 48740 KB Output is correct
5 Correct 161 ms 55092 KB Output is correct
6 Correct 159 ms 54976 KB Output is correct
7 Correct 161 ms 54988 KB Output is correct
8 Correct 165 ms 55100 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21392 KB Output is correct
2 Correct 10 ms 21444 KB Output is correct
3 Correct 9 ms 21332 KB Output is correct
4 Correct 10 ms 21432 KB Output is correct
5 Correct 9 ms 21332 KB Output is correct
6 Correct 10 ms 21420 KB Output is correct
7 Correct 10 ms 21332 KB Output is correct
8 Correct 12 ms 21332 KB Output is correct
9 Correct 11 ms 21464 KB Output is correct
10 Correct 12 ms 21684 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 11 ms 21596 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21392 KB Output is correct
2 Correct 10 ms 21444 KB Output is correct
3 Correct 9 ms 21332 KB Output is correct
4 Correct 10 ms 21432 KB Output is correct
5 Correct 9 ms 21332 KB Output is correct
6 Correct 10 ms 21420 KB Output is correct
7 Correct 10 ms 21332 KB Output is correct
8 Correct 12 ms 21332 KB Output is correct
9 Correct 11 ms 21464 KB Output is correct
10 Correct 12 ms 21684 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 11 ms 21596 KB Output is correct
15 Correct 10 ms 21476 KB Output is correct
16 Correct 12 ms 21756 KB Output is correct
17 Correct 64 ms 28596 KB Output is correct
18 Correct 59 ms 27984 KB Output is correct
19 Correct 54 ms 28100 KB Output is correct
20 Correct 51 ms 27476 KB Output is correct
21 Correct 50 ms 27340 KB Output is correct
22 Correct 103 ms 33136 KB Output is correct
23 Correct 25 ms 24020 KB Output is correct
24 Correct 56 ms 28276 KB Output is correct
25 Correct 12 ms 21744 KB Output is correct
26 Correct 23 ms 23672 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21392 KB Output is correct
2 Correct 10 ms 21444 KB Output is correct
3 Correct 9 ms 21332 KB Output is correct
4 Correct 10 ms 21432 KB Output is correct
5 Correct 9 ms 21332 KB Output is correct
6 Correct 10 ms 21420 KB Output is correct
7 Correct 10 ms 21332 KB Output is correct
8 Correct 12 ms 21332 KB Output is correct
9 Correct 11 ms 21464 KB Output is correct
10 Correct 12 ms 21684 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 11 ms 21596 KB Output is correct
15 Correct 10 ms 21476 KB Output is correct
16 Correct 12 ms 21756 KB Output is correct
17 Correct 64 ms 28596 KB Output is correct
18 Correct 59 ms 27984 KB Output is correct
19 Correct 54 ms 28100 KB Output is correct
20 Correct 51 ms 27476 KB Output is correct
21 Correct 50 ms 27340 KB Output is correct
22 Correct 103 ms 33136 KB Output is correct
23 Correct 25 ms 24020 KB Output is correct
24 Correct 56 ms 28276 KB Output is correct
25 Correct 12 ms 21744 KB Output is correct
26 Correct 23 ms 23672 KB Output is correct
27 Correct 16 ms 22572 KB Output is correct
28 Correct 328 ms 54308 KB Output is correct
29 Correct 641 ms 77192 KB Output is correct
30 Correct 911 ms 116612 KB Output is correct
31 Correct 848 ms 115800 KB Output is correct
32 Correct 417 ms 66156 KB Output is correct
33 Correct 892 ms 118416 KB Output is correct
34 Correct 976 ms 118224 KB Output is correct
35 Correct 223 ms 51396 KB Output is correct
36 Correct 962 ms 105668 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 44900 KB Output is correct
2 Correct 63 ms 44984 KB Output is correct
3 Correct 109 ms 48136 KB Output is correct
4 Correct 97 ms 48740 KB Output is correct
5 Correct 161 ms 55092 KB Output is correct
6 Correct 159 ms 54976 KB Output is correct
7 Correct 161 ms 54988 KB Output is correct
8 Correct 165 ms 55100 KB Output is correct
9 Correct 194 ms 59764 KB Output is correct
10 Correct 117 ms 41764 KB Output is correct
11 Correct 259 ms 62112 KB Output is correct
12 Correct 13 ms 21400 KB Output is correct
13 Correct 11 ms 21404 KB Output is correct
14 Correct 11 ms 21332 KB Output is correct
15 Correct 10 ms 21376 KB Output is correct
16 Correct 13 ms 21332 KB Output is correct
17 Correct 11 ms 21332 KB Output is correct
18 Correct 69 ms 44848 KB Output is correct
19 Correct 66 ms 44896 KB Output is correct
20 Correct 63 ms 44896 KB Output is correct
21 Correct 64 ms 44808 KB Output is correct
22 Correct 284 ms 70028 KB Output is correct
23 Correct 462 ms 81128 KB Output is correct
24 Correct 432 ms 83236 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 70052 KB Output is correct
2 Correct 311 ms 77964 KB Output is correct
3 Correct 60 ms 44884 KB Output is correct
4 Correct 60 ms 44896 KB Output is correct
5 Execution timed out 1091 ms 142376 KB Time limit exceeded
6 Halted 0 ms 0 KB -