Submission #626272

#	Time	Username	Problem	Language	Result	Execution time	Memory
626272		Antekb	메기 농장 (IOI22_fish)	C++17	0 / 100	172 ms	32404 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define st first
#define nd second
using namespace std;
using ll = long long;
const int INF=1e9+5;
ll max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
	for(auto &i:X)i++;
	vector<pair<int, int> > V[n+2];	
	vector<ll> dp[n+2][2];
	ll dp2[n+2][2];
	for(int i=0; i<=n+1; i++)dp2[i][0]=dp2[i][1]=0;
	for(int i=0; i<m; i++){
		V[X[i]].pb({Y[i], W[i]});
	}
	for(int i=0; i<=n+1; i++){
		V[i].pb({n, INF});
		sort(V[i].begin(), V[i].end());
		dp[i][0].resize(V[i].size());
		dp[i][1].resize(V[i].size());
	}
	dp[0][0][1]=dp[0][0][0]=-1e18;
	for(int i=1; i<=n+1; i++){
		ll s=0;
		int wsk=0;
		for(int j=0; j<V[i-1].size(); j++){
			dp[i-1][j][0]-=s;
			s+=V[i-1][j].nd;
		}
		ll m=dp2[i-1][0];
		dp2[i][0]=max(dp2[i-1][0], dp2[i-1][1]);
		s=0;
		for(int j=0; j<V[i].size(); j++){
			while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
				m=max(m, dp[i-1][wsk][0]);
				s+=V[i-1][wsk].nd;
				wsk++;
			}
			dp[i][j][0]=s+m;
		}
		wsk=V[i-1].size()-1;
		m=dp[i-1][wsk][1];
		for(int j=V[i].size()-2; j>=0; j--){
			while(wsk!=0 && V[i-1][wsk-1].st>V[i][j].st){
				m=max(m, dp[i-1][wsk-1][1]);
				wsk--;
			}
			dp[i][j][1]=m;
			m+=V[i][j].nd;
		}
		for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][j][1]);
		dp2[i][1]=max(m, dp2[i][0]);
		for(int j=0; j<V[i].size(); j++){
			dp[i][j][0]=max(dp[i][j][0], dp2[i-1][1]);
		}
		for(int j=0; j<V[i].size(); j++){
			dp[i][j][1]=max(dp[i][j][0], dp[i][j][1]);
		}
		//cout<<i<<"\n";
		//cout<<dp2[i][0]<<" "<<dp2[i][1]<<" a\n";
		for(int j=0; j<=V[i].size(); j++){
			//cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<" b\n";
		}
	}
	return dp2[n+1][0];
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int j=0; j<V[i-1].size(); j++){
      |                ~^~~~~~~~~~~~~~
fish.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:36:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    while(wsk<V[i-1].size() && V[i][j].st>V[i-1][wsk].st){
      |          ~~~^~~~~~~~~~~~~~
fish.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j=0; j<V[i-1].size(); j++)dp2[i][0]=max(dp2[i][0], dp[i-1][j][1]);
      |                ~^~~~~~~~~~~~~~
fish.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0; j<V[i].size(); j++){
      |                ~^~~~~~~~~~~~
fish.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int j=0; j<=V[i].size(); j++){
      |                ~^~~~~~~~~~~~~

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