제출 #838443

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

fish

#include "fish.h"
 
#include <vector>
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const int nx=1e5+5;
ll mx;
vector<vector<pair<ll, ll>>> v(nx), dp(nx), mx1(nx), mx2(nx), mx3(nx);
 
ll get_val(ll col, ll row)
{
    return prev(upper_bound(v[col].begin(), v[col].end(), make_pair(row, LLONG_MAX)))->second;
}
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  for (int i=0; i<M; i++) v[X[i]+1].push_back({Y[i]+1, W[i]});
  for (int i=0; i<=N+1  ; i++) v[i].push_back({0, 0}), sort(v[i].begin(), v[i].end());
  for (int i=1; i<=N; i++) for (int j=1; j<v[i].size(); j++) v[i][j].second+=v[i][j-1].second;
  mx1[0].push_back({0, 0}); mx2[0].push_back({N, -1e18}); mx3[0].push_back({0, 0});
  for (int i=1; i<=N; i++)
  {
    dp[i].push_back({0, 0});
    for (int j=1; j<v[i-1].size(); j++) dp[i].push_back({v[i-1][j].first, 0ll});
    for (int j=1; j<v[i+1].size(); j++) dp[i].push_back({v[i+1][j].first, 0ll});
    sort(dp[i].begin(), dp[i].end());
    for (int j=0; j<dp[i].size(); j++)
    {
      ll c=dp[i][j].first; dp[i][j].first=0;
      dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+get_val(i-1, c)+(prev(upper_bound(mx1[i-1].begin(), mx1[i-1].end(), make_pair(c, LLONG_MAX))))->second);
      dp[i][j].second=max(dp[i][j].second, get_val(i+1, c)-get_val(i, c)+(lower_bound(mx2[i-1].begin(), mx2[i-1].end(), make_pair(c, LLONG_MIN)))->second);
      if (i>=2) dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+(lower_bound(mx2[i-2].begin(), mx2[i-2].end(), make_pair(c, LLONG_MIN)))->second);
      if (i>=2) dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+get_val(i-1, c)+(prev(upper_bound(mx3[i-2].begin(), mx3[i-2].end(), make_pair(c, LLONG_MAX))))->second);
      mx1[i].push_back({c, dp[i][j].first-get_val(i, c)-get_val(i+1, c)});
      mx2[i].push_back({c, max(dp[i][j].first, dp[i][j].second)});
      mx3[i].push_back({c, max(dp[i][j].first, dp[i][j].second)-get_val(i+1, c)});
      //cout<<i<<' '<<c<<' '<<dp[i][j].first<<' '<<dp[i][j].second<<'\n';
      mx=max({mx, dp[i][j].first, dp[i][j].second});
    }
    for (int j=1; j<mx1[i].size(); j++) mx1[i][j].second=max(mx1[i][j].second, mx1[i][j-1].second);
    for (int j=mx1[i].size()-2; j>=0; j--) mx2[i][j].second=max(mx2[i][j].second, mx2[i][j+1].second);
    for (int j=1; j<mx1[i].size(); j++) mx3[i][j].second=max(mx3[i][j].second, mx3[i][j-1].second);
    mx2[i].push_back({N, -1e18});
  }
  return mx;
}

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

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:22:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int i=1; i<=N; i++) for (int j=1; j<v[i].size(); j++) v[i][j].second+=v[i][j-1].second;
      |                                          ~^~~~~~~~~~~~
fish.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int j=1; j<v[i-1].size(); j++) dp[i].push_back({v[i-1][j].first, 0ll});
      |                   ~^~~~~~~~~~~~~~
fish.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int j=1; j<v[i+1].size(); j++) dp[i].push_back({v[i+1][j].first, 0ll});
      |                   ~^~~~~~~~~~~~~~
fish.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int j=0; j<dp[i].size(); j++)
      |                   ~^~~~~~~~~~~~~
fish.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int j=1; j<mx1[i].size(); j++) mx1[i][j].second=max(mx1[i][j].second, mx1[i][j-1].second);
      |                   ~^~~~~~~~~~~~~~
fish.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int j=1; j<mx1[i].size(); j++) mx3[i][j].second=max(mx3[i][j].second, mx3[i][j-1].second);
      |                   ~^~~~~~~~~~~~~~

• 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