Submission #634608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
634608	2022-08-24T15:42:41 Z	l_reho	Catfish Farm (IOI22_fish)	C++17	9 / 100	93 ms	12216 KB

fish

#include "fish.h"

#include <cassert>
#include <cstdio>

// BEGIN SECRET
#include <string>
// END SECRET
#include <vector>

#include <bits/stdc++.h>
using namespace std;


vector<vector<int>> V;

struct info{
	int y;
	int w;
	int flag;
	
};


struct CustomCompare
{
	bool operator()(info const& p, info const& p1)
    {
        return (p.y > p1.y) || (p.y == p1.y && p.flag > p1.flag);
    }
};


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
	
	// se X[i] è pari, allora posso ergere ponti per prendere tutti
	
	bool subtask1 = true;
	bool subtask2 = true;
	bool subtask3 = true;
	bool subtask4 = true;
	
	long long ans = 0;
	
	// for(int i = 0; i < (int)X.size(); i++)
		// V[X[i]][Y[i]] = W[i];

	for(int i = 0; i < (int)X.size(); i++){
		subtask1 &= X[i] % 2 == 0;
		subtask2 &= X[i] <= 1;
		subtask3 &= Y[i] == 0;
		subtask4 &= N <= 300;
	}
	
	if(subtask1){
		ans = accumulate(W.begin(), W.end(), 0L);
		return ans;
	}
	
	if(subtask2){
		if(N == 1) return 0;
		
		if(N == 2){
			long long x0 = 0, x1 = 0;
			for(int i = 0; i < (int)X.size(); i++){
				if(X[i] == 1) x1 += W[i];
				else x0 += W[i];
			}	
			return max(x1, x0);
		}
		
		
		
		priority_queue<info, vector<info>, CustomCompare> pq;
		
		long long x1 = 0;
		for(int i = 0; i < (int)X.size(); i++){
			pq.push({Y[i], W[i], X[i] == 0});
			if(X[i] == 1) x1 += W[i];
		}
		
		long long curr = x1;
		
		ans = curr;
		while(!pq.empty()){
			info p = pq.top();
			pq.pop();
			
			
			if(p.flag) curr += p.w, ans = max(ans, curr);
			else curr -= p.w;
			
		}
		
		return ans;
		
	}
	
	if(subtask3){
		cout<<"CIAO"<<endl;
		long long dp[M][3];
		
		for(int i = 0; i < M; i++)
			for(int j = 0; j < 3; j++) dp[i][j] = 0;
		
		
		vector<pair<int, int>> V;
		
		for(int i = 0; i < M; i++) V.push_back({X[i], W[i]});
			
		sort(V.begin(), V.end());
		
		
		dp[0][0] = V[0].second;
		
		if(V[0].first != 0) {
					
			dp[0][1] = V[0].second;
		}
		
		dp[0][2] = max(dp[0][1], dp[0][0]);
		
		for(int i = 1; i < M; i++){
		
			if(abs(V[i].first-V[i-1].first) == 1){
				
				if(V[i].first < N-1)
					dp[i][0] = max(dp[i-1][1]+V[i].second, dp[i-1][0]);
			
				if(i >= 2){
					if(V[i].first < N-1)
						dp[i][0] = max(dp[i][0], dp[i-2][2]);
					dp[i][1] = dp[i-2][2] + V[i].second;
		
				}else dp[i][1] = V[i].second;
			
				dp[i][2] = max(dp[i-1][2], max(dp[i][0], dp[i][1]));
			}else{
				
				dp[i][1] = dp[i][2] = dp[i-1][2] + V[i].second;
				if(V[i].first < N-1)
					dp[i][0] = dp[i][1];
				
			}
		}
		
		
		return dp[M-1][2];
		
		
	}

	
	return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2636 KB	Output is correct
2	Correct	28 ms	4040 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	91 ms	12216 KB	Output is correct
6	Correct	91 ms	12176 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	78 ms	9756 KB	Output is correct
3	Correct	93 ms	11400 KB	Output is correct
4	Correct	23 ms	3276 KB	Output is correct
5	Correct	27 ms	4104 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	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	39 ms	5020 KB	Output is correct
13	Correct	46 ms	5744 KB	Output is correct
14	Correct	37 ms	5036 KB	Output is correct
15	Correct	43 ms	5312 KB	Output is correct
16	Correct	36 ms	4932 KB	Output is correct
17	Correct	41 ms	5352 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Possible tampering with the output
3	Halted	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	1st lines differ - on the 1st token, expected: '3', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Possible tampering with the output
3	Halted	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2636 KB	Output is correct
2	Correct	28 ms	4040 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	91 ms	12216 KB	Output is correct
6	Correct	91 ms	12176 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	78 ms	9756 KB	Output is correct
9	Correct	93 ms	11400 KB	Output is correct
10	Correct	23 ms	3276 KB	Output is correct
11	Correct	27 ms	4104 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	39 ms	5020 KB	Output is correct
19	Correct	46 ms	5744 KB	Output is correct
20	Correct	37 ms	5036 KB	Output is correct
21	Correct	43 ms	5312 KB	Output is correct
22	Correct	36 ms	4932 KB	Output is correct
23	Correct	41 ms	5352 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Incorrect	0 ms	212 KB	Possible tampering with the output
26	Halted	0 ms	0 KB	-

Submission #634608

Compilation message