제출 #635137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635137		l_reho	메기 농장 (IOI22_fish)	C++17	18 / 100	94 ms	8152 KiB

fish

#include "fish.h"

#include <cassert>
#include <cstdio>

#include <vector>

#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){
		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] = dp[i-1][1]+V[i].second;
			
				if(i >= 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];		
	}
	
	if(subtask4){
		long long mat[N][N];
		long long pref[N][N][2];
		long long suff[N][N][2];
		long long memo[N];
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				pref[i][j][0] = 0;
				pref[i][j][1] = 0;
				suff[i][j][0] = 0;
				suff[i][j][1] = 0;
			
				mat[i][j] = 0;
			}	
			memo[i] = 0;
		}
		
		for(int i = 0; i <  M; i++) mat[N-Y[i]-1][X[i]] = W[i];
		
		long long sum = 0;
		for(int i = N-1; i >= 0; i--){
			sum += mat[i][0];
			pref[i][0][0] = sum;
			memo[0] = max({memo[0], pref[i][0][0]});
		}
		
		sum = 0;
		for(int i = 0; i < N; i++){
			sum += mat[i][0];
			suff[i][0][0] = sum;
			memo[0] = max({memo[0], suff[i][0][0]});
		}
		
		
		for(int j = 1; j < N; j++){
			sum = 0;
			
			// popoliamo pref
			for(int i = N-1; i >= 0; i--){
				// il prefisso lo posso combinare con il prefisso della colonna precedente
				// o con il suffisso della colonna precedente, ma entrambi applicando la colonna a sinistra
				sum += mat[i][j];
				
				for(int k = 0; k < N; k++){
					
					if(j < N-1){
						pref[i][j][0] = max(pref[i][j][0], pref[k][j-1][1] + sum);
						pref[i][j][0] = max(pref[i][j][0], suff[k][j-1][1] + sum);
					}
					if(k < i)
						pref[i][j][1] = max(pref[i][j][1], suff[k][j-1][1] + sum);
					
				}
						
				pref[i][j][1] = max(pref[i][j][1], sum);
				if(j < N-1)
					pref[i][j][0] = max(pref[i][j][0], sum);
				
				if(j >= 2){
					
					if(j < N-1)
						pref[i][j][0] = max(pref[i][j][0], memo[j-2] + sum);					
					pref[i][j][1] = max(pref[i][j][1], memo[j-2] + sum);
				}
				
				memo[j] = max({memo[j], memo[j-1], max(pref[i][j][0], pref[i][j][1])});
				
			}
			
			// adesso dobbiamo popolare suff qui i cazzi sono peggiori
			
			sum = 0;
			
			for(int i = 0; i < N; i++){
				sum += mat[i][j];
				
				for(int k = 0; k < N; k++){
					
					if(j < N-1){
						suff[i][j][0] = max(suff[i][j][0], pref[k][j-1][1] + sum);
						suff[i][j][0] = max(suff[i][j][0], suff[k][j-1][1] + sum);
					}
					
					if(k > i && j < N-1){
						suff[i][j][0] = max(suff[i][j][0], pref[k][j-1][0] + sum);
					}
					
				}
				
				suff[i][j][1] = max(suff[i][j][1], sum);
				
				if(j < N-1)
					suff[i][j][0] = max(suff[i][j][0], sum);
				
				if(j >= 2){
					if(j < N-1)
						suff[i][j][0] = max(suff[i][j][0], memo[j-2] + sum);					
					suff[i][j][1] = max(suff[i][j][1], memo[j-2] + sum);
				}
				
				memo[j] = max({memo[j], memo[j-1], max(suff[i][j][0], suff[i][j][1])});
				
			}
			
		}
		return memo[N-1];
	}
 
	
	return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16