oj.uz

Submission #1056793

# Submission time Handle Problem Language Result Execution time Memory
1056793 2024-08-13T11:18:58 Z tolbi Catfish Farm (IOI22_fish) C++17
12 / 100
 281 ms 145740 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long max_weights(int32_t N, int32_t M, std::vector<int32_t> X, std::vector<int32_t> Y,
	std::vector<int32_t> W) {
	vector<vector<pair<int,int>>> poses(N);
	vector<int> minel(N,N);
	for (int i = 0; i < M; ++i)
	{
		minel[X[i]]=min(minel[X[i]],(int)Y[i]);
		poses[X[i]].push_back({Y[i],W[i]});
	}
	for (int i = 0; i < N; ++i)
	{
		if (minel[i]) poses[i].push_back({0,0});
		sort(poses[i].begin(), poses[i].end());
		poses[i].push_back({N,0});
	}
	vector<vector<vector<int>>> dp(N);
	for (int i = 0; i < N; ++i)
	{
		dp[i].resize(poses[i].size(),vector<int>(3,-1));
	}
	vector<vector<int>> pref(N);
	for (int i = 0; i < N; ++i)
	{
		pref[i].resize(poses[i].size());
		for (int j = 0; j < pref[i].size(); j++){
			pref[i][j]=poses[i][j].second;
			if (j) pref[i][j]+=pref[i][j-1];
		}
	}
	function<int(int,int,int)> query = [&](int node, int l, int r)->int{
		if (l>r) return 0;
		int ans = 0;
		int ilk = lower_bound(poses[node].begin(), poses[node].end(), pair<int,int>{r,0})-poses[node].begin();
		if (ilk==poses[node].size() || poses[node][ilk].first>r) ilk--;
		if (ilk<0) return 0;
		int hh = pref[node][ilk];
		ilk = lower_bound(poses[node].begin(), poses[node].end(), pair<int,int>{l,0})-poses[node].begin()-1;
		if (ilk>=0) hh-=pref[node][ilk];
		return hh;
	};
	function<int(int,int,int)> f = [&](int pos, int node, int flag)->int{
		if (pos==N) return 0;
		if (dp[pos][node][flag]!=-1) return dp[pos][node][flag];
		dp[pos][node][flag]=0;
		if (flag<=1){
			//0 artiyo
			//1 artiyo, arkadan ekleme
			if (node+1<dp[pos].size()){
				//bi yukari git
				int cur = f(pos,node+1,flag);
				if (flag==0 && pos){
					cur+=query(pos-1,poses[pos][node].first,poses[pos][node+1].first-1);
				}
				dp[pos][node][flag]=max(dp[pos][node][flag],cur);
			}
		}
		else {
			assert(node>0 && poses[pos][node].first>0);
			if (poses[pos][node-1].first>0){
				dp[pos][node][flag]=max(dp[pos][node][flag],f(pos,node-1,flag)+poses[pos][node-1].second);
			}
		}
		if (pos+1<N){
			int buyu = lower_bound(poses[pos+1].begin(),poses[pos+1].end(),pair<int,int>{poses[pos][node].first,0})-poses[pos+1].begin();
			if (flag<=1 && buyu<poses[pos+1].size()){
				dp[pos][node][flag]=max(dp[pos][node][flag],f(pos+1,buyu,0)+query(pos,poses[pos][node].first,poses[pos+1][buyu].first-1));
				if (buyu>0){
					dp[pos][node][flag]=max(dp[pos][node][flag],f(pos+1,buyu,2)+query(pos,poses[pos][node].first,poses[pos+1][buyu].first-1));
				}
			}
			if (buyu==poses[pos+1].size() || poses[pos+1][buyu].first!=poses[pos][node].first) buyu--;
			if (buyu>0){
				dp[pos][node][flag]=max(dp[pos][node][flag],f(pos+1,buyu,2))+query(pos+1,poses[pos+1][buyu].first,poses[pos][node].first-1);
			}
		}
		if (pos+2<N){
			dp[pos][node][flag]=max(dp[pos][node][flag],f(pos+2,0,0));
			dp[pos][node][flag]=max(dp[pos][node][flag],f(pos+2,0,1)+query(pos+1,0,poses[pos][node].first-1));
		}
		else if (pos+1<N) {
			dp[pos][node][flag]=max(dp[pos][node][flag],query(pos+1,0,poses[pos][node].first-1));
		}
		return dp[pos][node][flag];
	};
	return f(0,0,0);
}

Compilation message

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:29:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int j = 0; j < pref[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
fish.cpp: In lambda function:
fish.cpp:38:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if (ilk==poses[node].size() || poses[node][ilk].first>r) ilk--;
      |       ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:36:7: warning: unused variable 'ans' [-Wunused-variable]
   36 |   int ans = 0;
      |       ^~~
fish.cpp: In lambda function:
fish.cpp:52:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if (node+1<dp[pos].size()){
      |        ~~~~~~^~~~~~~~~~~~~~~
fish.cpp:69:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    if (flag<=1 && buyu<poses[pos+1].size()){
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:75:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    if (buyu==poses[pos+1].size() || poses[pos+1][buyu].first!=poses[pos][node].first) buyu--;
      |        ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 114016 KB Output is correct
2 Correct 127 ms 132600 KB Output is correct
3 Correct 69 ms 75344 KB Output is correct
4 Correct 68 ms 75348 KB Output is correct
5 Correct 281 ms 145740 KB Output is correct
6 Correct 230 ms 107860 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 157 ms 122484 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '44594597296154'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 75352 KB Output is correct
2 Correct 70 ms 75428 KB Output is correct
3 Correct 77 ms 69428 KB Output is correct
4 Correct 81 ms 76608 KB Output is correct
5 Correct 91 ms 78420 KB Output is correct
6 Correct 116 ms 78420 KB Output is correct
7 Correct 91 ms 78400 KB Output is correct
8 Correct 91 ms 78420 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '333740475667'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '333740475667'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '333740475667'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 75352 KB Output is correct
2 Correct 70 ms 75428 KB Output is correct
3 Correct 77 ms 69428 KB Output is correct
4 Correct 81 ms 76608 KB Output is correct
5 Correct 91 ms 78420 KB Output is correct
6 Correct 116 ms 78420 KB Output is correct
7 Correct 91 ms 78400 KB Output is correct
8 Correct 91 ms 78420 KB Output is correct
9 Correct 118 ms 85840 KB Output is correct
10 Correct 74 ms 44368 KB Output is correct
11 Correct 144 ms 88584 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 70 ms 75568 KB Output is correct
19 Correct 70 ms 75408 KB Output is correct
20 Correct 71 ms 75348 KB Output is correct
21 Correct 69 ms 75344 KB Output is correct
22 Incorrect 134 ms 85788 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '60939657596223'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 114016 KB Output is correct
2 Correct 127 ms 132600 KB Output is correct
3 Correct 69 ms 75344 KB Output is correct
4 Correct 68 ms 75348 KB Output is correct
5 Correct 281 ms 145740 KB Output is correct
6 Correct 230 ms 107860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 157 ms 122484 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '44594597296154'
9 Halted 0 ms 0 KB -