답안 #627249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
627249 2022-08-12T11:38:15 Z czhang2718 메기 농장 (IOI22_fish) C++17
3 / 100
246 ms 66056 KB
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define f first
#define s second

const int N=3e5+4;
int n,m;
vector<pair<int,int>> fish[N];
vector<ll> dp[N], dp1[N], inc[N];

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++){
      fish[X[i]+1].push_back({Y[i], W[i]});
  }

  for(int i=1; i<=n; i++){
      fish[i].push_back({0, 0});
      fish[i].push_back({n, 0});
      sort(fish[i].begin(), fish[i].end());
  }

  int i=0;
  fish[i].push_back({0, 0});
  dp[i].resize(2);
  dp1[i].resize(2);
  inc[i].resize(2);
  for(int i=1; i<=n; i++){
      int p=fish[i].size();
      if(p>1 && fish[i][1].f==fish[i][0].f) fish[i].erase(fish[i].begin());
      dp[i].resize(p+1, -1e18);
      dp1[i].resize(p+1, -1e18);
      inc[i].resize(p+1, -1e18);
      ll sum=0;
      pair<int, ll> nxt, prv;
      for(int j=0; j<p; j++){
          auto fi=fish[i][j];
          int y=fi.f, w=fi.s;
          while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
              nxt.s+=fish[i+1][nxt.f].s;
              nxt.f++;
          }
          while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
              prv.s+=fish[i-1][prv.f].s;
              prv.f++;
          }
          int k=upper_bound(fish[i-1].begin(), fish[i-1].end(), make_pair(y, 0))-fish[i-1].begin();
          dp[i][j]=max(dp1[i-1][k]-sum, fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0);
          // cout << "inc " << prv.s+(fish[i-1][k-1].f?inc[i-1][k-1]:0) << "\n";
          int k2;
          if(i>=2){
              k2=upper_bound(fish[i-2].begin(), fish[i-2].end(), make_pair(y, 0))-fish[i-2].begin();
              dp[i][j]=max({dp[i][j], dp1[i-2][k2], (k2?dp[i-2][k2-1]:0)+prv.s});
          }
          inc[i][j]=max(
              j?inc[i][j-1]:0, 
              -sum + max(fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0, i>=2?max(dp1[i-2][k2], dp[i-2][k2-1]+prv.s):0));
          sum+=w;
          // cout << "inc[" << i << "][" << j << "] " << inc[i][j] << "\n";
          // cout << "dp[" << i << "][" << j << "] " << dp[i][j] << "\n";
          dp1[i][j]=dp[i][j]+nxt.s;
      }

      for(int j=p-1; j>=0; j--){
          dp1[i][j]=max(dp1[i][j+1], dp1[i][j]);
      }
  }

  return dp1[n][0];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |           while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
      |                 ~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |           while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
      |                 ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 45520 KB Output is correct
2 Correct 87 ms 48188 KB Output is correct
3 Correct 49 ms 40932 KB Output is correct
4 Correct 46 ms 40920 KB Output is correct
5 Correct 174 ms 63728 KB Output is correct
6 Correct 246 ms 66056 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 28440 KB 1st lines differ - on the 1st token, expected: '2', found: '50'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 40896 KB Output is correct
2 Correct 47 ms 40956 KB Output is correct
3 Correct 70 ms 45352 KB Output is correct
4 Correct 87 ms 44472 KB Output is correct
5 Incorrect 109 ms 50620 KB 1st lines differ - on the 1st token, expected: '1673106170551', found: '1673106170600'
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '51'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '51'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '51'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 40896 KB Output is correct
2 Correct 47 ms 40956 KB Output is correct
3 Correct 70 ms 45352 KB Output is correct
4 Correct 87 ms 44472 KB Output is correct
5 Incorrect 109 ms 50620 KB 1st lines differ - on the 1st token, expected: '1673106170551', found: '1673106170600'
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 45520 KB Output is correct
2 Correct 87 ms 48188 KB Output is correct
3 Correct 49 ms 40932 KB Output is correct
4 Correct 46 ms 40920 KB Output is correct
5 Correct 174 ms 63728 KB Output is correct
6 Correct 246 ms 66056 KB Output is correct
7 Incorrect 17 ms 28440 KB 1st lines differ - on the 1st token, expected: '2', found: '50'
8 Halted 0 ms 0 KB -