oj.uz

Submission #1056792

# Submission time Handle Problem Language Result Execution time Memory
1056792 2024-08-13T11:17:33 Z tolbi Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 117068 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;
		for (int i = 0; i < poses[node].size(); i++){
			if (poses[node][i].first>=l && poses[node][i].first<=r){
				ans+=poses[node][i].second;
			}
		}return ans;
	};
	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:37:21: 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]
   37 |   for (int i = 0; i < poses[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp: In lambda function:
fish.cpp:50: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]
   50 |    if (node+1<dp[pos].size()){
      |        ~~~~~~^~~~~~~~~~~~~~~
fish.cpp:67: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]
   67 |    if (flag<=1 && buyu<poses[pos+1].size()){
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:73: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]
   73 |    if (buyu==poses[pos+1].size() || poses[pos+1][buyu].first!=poses[pos][node].first) buyu--;
      |        ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 108736 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 348 KB Output is correct
2 Execution timed out 1099 ms 117068 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 72276 KB Output is correct
2 Correct 73 ms 72428 KB Output is correct
3 Correct 71 ms 66796 KB Output is correct
4 Correct 71 ms 74088 KB Output is correct
5 Correct 95 ms 76612 KB Output is correct
6 Correct 90 ms 76112 KB Output is correct
7 Correct 86 ms 76628 KB Output is correct
8 Correct 88 ms 76624 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 0 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 0 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 0 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 63 ms 72276 KB Output is correct
2 Correct 73 ms 72428 KB Output is correct
3 Correct 71 ms 66796 KB Output is correct
4 Correct 71 ms 74088 KB Output is correct
5 Correct 95 ms 76612 KB Output is correct
6 Correct 90 ms 76112 KB Output is correct
7 Correct 86 ms 76628 KB Output is correct
8 Correct 88 ms 76624 KB Output is correct
9 Correct 118 ms 84408 KB Output is correct
10 Correct 65 ms 44636 KB Output is correct
11 Correct 135 ms 88908 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 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 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 71 ms 72344 KB Output is correct
19 Correct 63 ms 72272 KB Output is correct
20 Correct 63 ms 72276 KB Output is correct
21 Correct 62 ms 72208 KB Output is correct
22 Incorrect 117 ms 85024 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 Execution timed out 1014 ms 108736 KB Time limit exceeded
2 Halted 0 ms 0 KB -