제출 #639772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639772		study	메기 농장 (IOI22_fish)	C++17	100 / 100	296 ms	84064 KiB

fish

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

const int MAXN = 1e5+1;

vector<long long> dp[3][MAXN];
vector<pair<int,long long>> grid[MAXN],init[MAXN];

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
	for (int i=0; i<N; ++i) grid[i].emplace_back(0,0);
	for (int i=0; i<M; ++i){
		Y[i]++;
		init[X[i]].emplace_back(Y[i],W[i]);
		if (X[i]-1 >= 0) init[X[i]-1].emplace_back(Y[i],0);
		if (X[i]+1 < N) init[X[i]+1].emplace_back(Y[i],0);
	}
	for (int i=0; i<N; ++i){
		sort(init[i].begin(),init[i].end());
		for (auto k:init[i]){
			if (grid[i].back().first == k.first) grid[i].back().second += k.second;
			else grid[i].emplace_back(k);
		}
	}
	dp[0][0] = vector<long long>(grid[0].size());
	dp[1][0] = vector<long long>(grid[0].size());
	dp[2][0].emplace_back(0);
	long long ans = 0;
	for (int x=1; x<N; ++x){
		int siz = grid[x].size();
		dp[0][x] = vector<long long>(siz);
		dp[1][x] = vector<long long>(siz);
		dp[2][x].emplace_back(0);
		long long sum = 0, best = 0, sum2 = 0, sum3 = 0, idx2 = 0;
		for (int idx=0; idx<grid[x].size(); ++idx){
			while (idx2 < grid[x-1].size() and grid[x-1][idx2].first <= grid[x][idx].first){
				sum += grid[x-1][idx2].second;
				sum = max(sum,dp[1][x-1][idx2]);
				idx2++;
			}
			if (idx == 0) sum = max(sum,dp[2][x-1][0]);
			if (idx == 0) best = max(best,dp[0][x-1][0]);
			dp[1][x][idx] = max(best,sum);
			ans = max({best,sum,ans});
		}
		idx2 = grid[x-1].size()-1;
		for (int idx=grid[x].size()-1; idx>=0; --idx){
			while (idx2 >= 0 and grid[x-1][idx2].first >= grid[x][idx].first){
				sum2 = max({sum2,dp[1][x-1][idx2],dp[0][x-1][idx2]});
				sum3 = max({sum3,dp[1][x-1][idx2],dp[0][x-1][idx2]});
				idx2--;
			}
			dp[0][x][idx] = sum2;
			dp[2][x][0] = max(dp[2][x][0],sum3);
			ans = max({ans,sum2,dp[2][x][0]});
			sum2 += grid[x][idx].second;
		}
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int idx=0; idx<grid[x].size(); ++idx){
      |                   ~~~^~~~~~~~~~~~~~~
fish.cpp:36:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    while (idx2 < grid[x-1].size() and grid[x-1][idx2].first <= grid[x][idx].first){
      |           ~~~~~^~~~~~~~~~~~~~~~~~

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