oj.uz

Submission #836937

# Submission time Handle Problem Language Result Execution time Memory
836937 2023-08-24T17:28:35 Z MeGustaElArroz23 Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 2097152 KB 
#include "fish.h"

#include <vector>

#include<bits/stdc++.h>

using namespace std;

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {

#define ll long long
#define vi vector<long long>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vb vector<bool>
#define pii pair<long long,long long>
#define vii vector<pii>
#define vvii vector<vii>
#define pb push_back
#define fi first
#define se second

	vvi posh(n);
	for (int i=0;i<m;i++) posh[x[i]].pb(y[i]-1);
	for (int i=0;i<n;i++) posh[i].pb(n-1);

	for (int i=0;i<n;i++) sort(posh[i].begin(),posh[i].end());

	vvii cats(n);
	for (int i=0;i<m;i++) cats[x[i]].pb(pii{y[i],w[i]});
	//for (int i=0;i<n;i++) cats[i].pb(pii{n,0});

	for (int i=0;i<n;i++) sort(cats[i].begin(),cats[i].end());


	//cerr << "HHHHHHHHHHHHHH\n";

	vvi pref(n,vi(n+1,0));
	for (int i=0;i<n;i++){
		int k=0;
		for (int j=1;j<=n;j++){
			if (k<cats[i].size() && cats[i][k].fi==j-1){
				pref[i][j]=pref[i][j-1]+cats[i][k].se;
				k++;
			}
			else pref[i][j]=pref[i][j-1];
		}
	}

	//cerr << "HHHHHHHHHHHHHH\n";

	vvvi dp(n); //columna, h[i], h[i-1]

	//hago dp[1]

	dp[1]=vvi(posh[1].size(),vi(posh[0].size(),0));

	for (int i=0;i<posh[1].size();i++){
		for (int j=0;j<posh[0].size();j++){
			if (posh[1][i]>posh[0][j]) 
				dp[1][i][j]=pref[0][posh[1][i]+1]-pref[0][posh[0][j]+1];
			else
				dp[1][i][j]=pref[1][posh[0][j]+1]-pref[1][posh[1][i]+1];

			//cerr << "1: "<< i << ' ' << j << ' ' << dp[1][i][j] << '\n';
		}
	}

	//
	//cerr << "HHHHHHHHHHHHHH\n";

	for (int i=2;i<n;i++){
		dp[i]=vvi(posh[i].size(),vi(posh[i-1].size(),0));
		for (int j=0;j<posh[i].size();j++){ //altura
			for (int k=0;k<posh[i-1].size();k++){ //altura ant
				for (int l=0;l<posh[i-2].size();l++){

					ll ans=dp[i-1][k][l];

					if (posh[i][j]>posh[i-1][k]){
						if (posh[i][j]>posh[i-2][l])
							ans+=pref[i-1][posh[i][j]+1]-pref[i-1][
								max(posh[i-2][l],posh[i-1][k]) +1];
					}
					else
						ans+=pref[i][posh[i-1][k]+1]-pref[i][posh[i][j]+1];

					dp[i][j][k]=max(dp[i][j][k],ans);
					//cerr << i << ": " << posh[i][j] << ' ' << posh[i-1][k] << ' ' << dp[i][j][k] << '\n';
				}
			}
		}
	}

	//cerr << "HHHHHHHHHHHHHH\n";

	ll res=0;
	for (vi v:dp[n-1]){
		for (ll b:v) res=max(res,b);
		
	}

	return res;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (k<cats[i].size() && cats[i][k].fi==j-1){
      |        ~^~~~~~~~~~~~~~~
fish.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=0;i<posh[1].size();i++){
      |               ~^~~~~~~~~~~~~~~
fish.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int j=0;j<posh[0].size();j++){
      |                ~^~~~~~~~~~~~~~~
fish.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int j=0;j<posh[i].size();j++){ //altura
      |                ~^~~~~~~~~~~~~~~
fish.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int k=0;k<posh[i-1].size();k++){ //altura ant
      |                 ~^~~~~~~~~~~~~~~~~
fish.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int l=0;l<posh[i-2].size();l++){
      |                  ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1148 ms 1896552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 827 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 1496 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 1120 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 1496 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 1120 KB Output is correct
15 Correct 1 ms 992 KB Output is correct
16 Correct 11 ms 1504 KB Output is correct
17 Execution timed out 1073 ms 32032 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 1496 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 1120 KB Output is correct
15 Correct 1 ms 992 KB Output is correct
16 Correct 11 ms 1504 KB Output is correct
17 Execution timed out 1073 ms 32032 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 676 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1148 ms 1896552 KB Time limit exceeded
2 Halted 0 ms 0 KB -