Submission #800389

#	Time	Username	Problem	Language	Result	Execution time	Memory
800389		Ronin13	Catfish Farm (IOI22_fish)	C++17	9 / 100	605 ms	151176 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

map <pii, ll> mp;
const int nmax = 300001;

vector <vector <int> > ff(nmax);
vector <vector <int> > pos(nmax);
vector <vector <ll> > smx(nmax), pmx(nmax);
vector <vector <ll> > pref(nmax);
long long max_weights(int n, int m, vector<int> x, vector<int> y,vector<int> w) {
  
  for(int i = 0; i < m; i++){
    x[i]++;
    y[i]++;
    mp[{x[i], y[i]}] = w[i];
    ff[x[i]].pb(y[i]); 
  }
  for(int i= 1; i <= n; i++){
      for(int j : ff[i - 1]) pos[i].pb(j);
      for(int j : ff[i + 1]) pos[i].pb(j);
      for(int j : ff[i]) pos[i].pb(j);
      pos[i].pb(-1);
      pos[i].pb(n + 1);
      sort(pos[i].begin(), pos[i].end());
      pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
      
      pref[i].resize(pos[i].size());
      
      
      pref[i][0] = mp[{i, pos[i][0]}];
      for(int j = 1; j < pref[i].size(); ++j){
          pref[i][j] = pref[i][j - 1] + mp[{i, pos[i][j]}];
      }
  }
  ll p;
  for(int i = 1; i <= n; i++){
      vector <ll> dp, DP;
      dp.resize(pos[i].size());
      DP.resize(pos[i].size());
      smx[i].resize(pos[i].size());
      pmx[i].resize(pos[i].size());
      if(i == 1){
        fill(dp.begin(), dp.end(), 0);
        fill(DP.begin(), DP.end(), 0);
        p = dp[0];
      }
      else{
          for(int j = 0; j < pos[i].size(); j++){
              int val = pos[i][j];
              int u = lower_bound(pos[i - 1].begin(), pos[i - 1].end(), val) - pos[i - 1].begin();
             // cout << u << ' ';
              dp[j] = smx[i - 1][u] - pref[i][j];
              u = upper_bound(pos[i - 1].begin(), pos[i - 1].end(), val) - pos[i - 1].begin();
              
              DP[j] = pmx[i - 1][u - 1] + pref[i - 1][u - 1];
          }
         // DP[0] = max(DP[0], pmx[i - 1].back());
          dp.back() = max(dp.back(), DP.back());
          DP[0] = max(DP[0], p);
          p = dp[0];
      }
      if(i == n)
        return max(dp[0], DP.back());
      int o = upper_bound(pos[i + 1].begin(), pos[i + 1].end(), pos[i].back()) - 
              pos[i + 1].begin() - 1;
      smx[i].back() = dp.back() + pref[i + 1][o];
      for(int j = pos[i].size() - 2; j >= 0; j--){
        int val = pos[i][j];
        int o = upper_bound(pos[i + 1].begin(), pos[i + 1].end(), val) - pos[i + 1].begin() - 1;
        smx[i][j] = max(smx[i][j + 1], dp[j] + pref[i + 1][o]);
      }
      pmx[i][0] = DP[0]- pref[i][0];
      for(int j = 1; j < pos[i].size(); j++){
          pmx[i][j] = max(pmx[i][j - 1], DP[j] - pref[i][j]);
      }
      
  }

  return 0;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |       for(int j = 1; j < pref[i].size(); ++j){
      |                      ~~^~~~~~~~~~~~~~~~
fish.cpp:59:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |           for(int j = 0; j < pos[i].size(); j++){
      |                          ~~^~~~~~~~~~~~~~~
fish.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |       for(int j = 1; j < pos[i].size(); j++){
      |                      ~~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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