oj.uz

Submission #834384

# Submission time Handle Problem Language Result Execution time Memory
834384 2023-08-22T13:53:47 Z Rafi22 Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 147032 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<pair<int,int>,int>>P;
		for(auto [y,c]:V[i-1]) P.pb({{y,-c},1});
		for(auto [y,c]:V[i]) P.pb({{y,-c},2});
		for(auto [y,c]:V[i+1]) P.pb({{y,-c},3});
		for(int j=0;j<sz(points[i]);j++) P.pb({{points[i][j],j},0});
		sort(all(P));
		ll sum1=0,sum2=0,sum3=0;
		for(auto [y,c]:P)
		{
			if(c==0) 
			{
				L[i][y.nd]=sum1;
				M[i][y.nd]=sum2;
				R[i][y.nd]=sum3;
			}
			else if(c==1) sum1+=(ll)-y.nd;
			else if(c==2) sum2+=(ll)-y.nd;
			else sum3+=(ll)-y.nd;
		}
	}
	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 250 ms 68308 KB Output is correct
2 Correct 324 ms 77868 KB Output is correct
3 Correct 72 ms 44876 KB Output is correct
4 Correct 54 ms 44800 KB Output is correct
5 Execution timed out 1047 ms 147032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Correct 477 ms 83208 KB Output is correct
3 Correct 612 ms 96092 KB Output is correct
4 Correct 262 ms 69764 KB Output is correct
5 Correct 321 ms 77952 KB Output is correct
6 Correct 10 ms 21332 KB Output is correct
7 Correct 11 ms 21468 KB Output is correct
8 Correct 12 ms 21332 KB Output is correct
9 Correct 10 ms 21332 KB Output is correct
10 Correct 57 ms 44912 KB Output is correct
11 Correct 71 ms 44904 KB Output is correct
12 Correct 298 ms 73472 KB Output is correct
13 Correct 386 ms 82292 KB Output is correct
14 Correct 247 ms 71592 KB Output is correct
15 Correct 229 ms 69116 KB Output is correct
16 Correct 256 ms 71624 KB Output is correct
17 Correct 289 ms 76792 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 44900 KB Output is correct
2 Correct 57 ms 44852 KB Output is correct
3 Correct 108 ms 49100 KB Output is correct
4 Correct 106 ms 49328 KB Output is correct
5 Correct 169 ms 56628 KB Output is correct
6 Correct 158 ms 56012 KB Output is correct
7 Correct 167 ms 56612 KB Output is correct
8 Correct 163 ms 56552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21456 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21332 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 13 ms 21332 KB Output is correct
7 Correct 10 ms 21448 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 13 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21588 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21456 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21332 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 13 ms 21332 KB Output is correct
7 Correct 10 ms 21448 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 13 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21588 KB Output is correct
15 Correct 11 ms 21460 KB Output is correct
16 Correct 13 ms 21836 KB Output is correct
17 Correct 66 ms 29412 KB Output is correct
18 Correct 61 ms 28748 KB Output is correct
19 Correct 60 ms 28876 KB Output is correct
20 Correct 55 ms 28108 KB Output is correct
21 Correct 55 ms 28108 KB Output is correct
22 Correct 105 ms 34760 KB Output is correct
23 Correct 26 ms 24200 KB Output is correct
24 Correct 56 ms 28700 KB Output is correct
25 Correct 13 ms 21716 KB Output is correct
26 Correct 23 ms 23768 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21456 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21332 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 11 ms 21332 KB Output is correct
6 Correct 13 ms 21332 KB Output is correct
7 Correct 10 ms 21448 KB Output is correct
8 Correct 11 ms 21332 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 13 ms 21716 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 13 ms 21716 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21588 KB Output is correct
15 Correct 11 ms 21460 KB Output is correct
16 Correct 13 ms 21836 KB Output is correct
17 Correct 66 ms 29412 KB Output is correct
18 Correct 61 ms 28748 KB Output is correct
19 Correct 60 ms 28876 KB Output is correct
20 Correct 55 ms 28108 KB Output is correct
21 Correct 55 ms 28108 KB Output is correct
22 Correct 105 ms 34760 KB Output is correct
23 Correct 26 ms 24200 KB Output is correct
24 Correct 56 ms 28700 KB Output is correct
25 Correct 13 ms 21716 KB Output is correct
26 Correct 23 ms 23768 KB Output is correct
27 Correct 15 ms 22612 KB Output is correct
28 Correct 332 ms 58164 KB Output is correct
29 Correct 626 ms 82612 KB Output is correct
30 Correct 825 ms 116868 KB Output is correct
31 Correct 806 ms 116148 KB Output is correct
32 Correct 428 ms 66276 KB Output is correct
33 Correct 849 ms 118756 KB Output is correct
34 Correct 862 ms 118732 KB Output is correct
35 Correct 209 ms 51424 KB Output is correct
36 Correct 777 ms 106080 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 44900 KB Output is correct
2 Correct 57 ms 44852 KB Output is correct
3 Correct 108 ms 49100 KB Output is correct
4 Correct 106 ms 49328 KB Output is correct
5 Correct 169 ms 56628 KB Output is correct
6 Correct 158 ms 56012 KB Output is correct
7 Correct 167 ms 56612 KB Output is correct
8 Correct 163 ms 56552 KB Output is correct
9 Correct 176 ms 61132 KB Output is correct
10 Correct 116 ms 43408 KB Output is correct
11 Correct 275 ms 65612 KB Output is correct
12 Correct 12 ms 21332 KB Output is correct
13 Correct 10 ms 21440 KB Output is correct
14 Correct 9 ms 21332 KB Output is correct
15 Correct 10 ms 21332 KB Output is correct
16 Correct 13 ms 21332 KB Output is correct
17 Correct 10 ms 21332 KB Output is correct
18 Correct 60 ms 44912 KB Output is correct
19 Correct 53 ms 44884 KB Output is correct
20 Correct 59 ms 44912 KB Output is correct
21 Correct 69 ms 44904 KB Output is correct
22 Correct 257 ms 72020 KB Output is correct
23 Correct 378 ms 84592 KB Output is correct
24 Correct 407 ms 87296 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 68308 KB Output is correct
2 Correct 324 ms 77868 KB Output is correct
3 Correct 72 ms 44876 KB Output is correct
4 Correct 54 ms 44800 KB Output is correct
5 Execution timed out 1047 ms 147032 KB Time limit exceeded
6 Halted 0 ms 0 KB -