Submission #1046759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046759		Trent	Catfish Farm (IOI22_fish)	C++17	100 / 100	794 ms	145116 KiB

fish

    #include "fish.h"
    #include "bits/stdc++.h";
    using namespace std;
    #define forR(i, x) for(int i = 0; i < (x); ++i)
    #define REP(i, a, b) for(int i = (a); i < (b); ++i)
    #define all(x) x.begin(), x.end()
    typedef long long ll;
    typedef vector<ll> vll;
    typedef vector<vll> vvll;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    struct pii{int a, b;};
     
    ll INF = 1e16;
     
    ll rSum(int i, vector<pii>& wx, vll& psa) {
      int ind = upper_bound(all(wx), i, [](int a, pii b){return a < b.a;}) - wx.begin();
      if(ind - 1 == -1) return 0;
      return psa[ind-1];
    }
     
    long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                          std::vector<int> W) {
      vector<vector<pii>> wx(N);
      forR(i, M) wx[X[i]].push_back({Y[i], W[i]});
      forR(i, N) sort(all(wx[i]), [](pii a, pii b){return a.a < b.a;});
      vvll wpsa(N);
      forR(i, N) if(!wx[i].empty()) {
        wpsa[i].push_back(wx[i][0].b);
        REP(j, 1, wx[i].size()) wpsa[i].push_back(wx[i][j].b + wpsa[i].back());
      }
     
      vector<set<int>> sCare(N);
      forR(i, M) {
        if(X[i] > 0) sCare[X[i]-1].insert(Y[i] + 1);
        if(X[i] + 1 < N) sCare[X[i] + 1].insert(Y[i] + 1);
        if(X[i] + 2 < N) sCare[X[i] + 2].insert(Y[i] + 1);
        sCare[X[i]].insert(Y[i]+1);
      }
      forR(i, N) sCare[i].insert(0);
      vector<vi> care(N);
      forR(i, N) for(int j : sCare[i]) care[i].push_back(j);
      vvll I(N), D(N), E(N);
      forR(i, N) I[i].resize(care[i].size()), D[i].resize(care[i].size()), E[i].resize(care[i].size());
      // h = HEIGHT, not the index of last element!
      forR(i, N) {
        ll besIE = -INF, besII = -INF;
        if(i > 0) {
          forR(ki, care[i-1].size()) {
            int k = care[i-1][ki];
            besIE = max(besIE, E[i-1][ki] - rSum(k-1, wx[i-1], wpsa[i-1]));
          }
        }
        int api = 0;
        forR(hi, care[i].size()) {
          int h = care[i][hi];
          if(h > 0) {
            if(i == 0) I[i][hi] = 0;
            else {
              I[i][hi] = max(I[i][hi], besIE + rSum(h-1, wx[i-1], wpsa[i-1]));
              while(api < care[i-1].size() && care[i-1][api] <= h) {
                int k = care[i-1][api];
                besII = max(besII, I[i-1][api] - rSum(k-1, wx[i-1], wpsa[i-1]));
                ++api;
              }
              I[i][hi] = max(I[i][hi], besII + rSum(h-1, wx[i-1], wpsa[i-1]));
            }
          }
        }
     
        api = (int) care[i-1].size() - 1;
        ll besD = -INF;
        for(int hi = (int) care[i].size() - 1; hi >= 0; --hi){
          int h = care[i][hi];
          if(h > 0) {
            if(i == 0) D[i][hi] = 0;
            else {
              while(api >= 0 && care[i-1][api] >= h + 1) {
                int k = care[i-1][api];
                besD = max(besD, max(I[i-1][api], D[i-1][api]) + rSum(k-1, wx[i], wpsa[i]));
                --api;
              }
              D[i][hi] = max(D[i][hi], besD - rSum(h-1, wx[i], wpsa[i]));
            }
          }
        }
     
        ll besE = -INF;
        if(i > 0) {
          forR(yi, care[i-1].size()) besE = max(besE, E[i-1][yi]);
        }
        forR(hi, care[i].size()){
          int h = care[i][hi];
          if(i == 0) E[i][hi] = 0;
          else {
            int pInd = lower_bound(all(care[i-1]), h) - care[i-1].begin();
            if(care[i-1][pInd] == h) {
              ll tot = max(I[i-1][pInd], D[i-1][pInd]) + rSum(h-1, wx[i], wpsa[i]);
              E[i][hi] = max(E[i][hi], max(tot, besE));
            }
          }
        }
      }
      ll mx = 0;
      forR(hi, care[N-1].size()) if(care[N-1][hi] > 0) mx = max(mx, max(I[N-1][hi], D[N-1][hi]));
      forR(hi, care[N-1].size()) mx = max(mx, E[N-1][hi]);
      return mx;
    }

Compilation message (stderr)

fish.cpp:2:29: warning: extra tokens at end of #include directive
    2 |     #include "bits/stdc++.h";
      |                             ^
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:5:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     #define REP(i, a, b) for(int i = (a); i < (b); ++i)
      |                                             ^
fish.cpp:30:9: note: in expansion of macro 'REP'
   30 |         REP(j, 1, wx[i].size()) wpsa[i].push_back(wx[i][j].b + wpsa[i].back());
      |         ^~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:49:11: note: in expansion of macro 'forR'
   49 |           forR(ki, care[i-1].size()) {
      |           ^~~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:55:9: note: in expansion of macro 'forR'
   55 |         forR(hi, care[i].size()) {
      |         ^~~~
fish.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |               while(api < care[i-1].size() && care[i-1][api] <= h) {
      |                     ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:90:11: note: in expansion of macro 'forR'
   90 |           forR(yi, care[i-1].size()) besE = max(besE, E[i-1][yi]);
      |           ^~~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:92:9: note: in expansion of macro 'forR'
   92 |         forR(hi, care[i].size()){
      |         ^~~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:105:7: note: in expansion of macro 'forR'
  105 |       forR(hi, care[N-1].size()) if(care[N-1][hi] > 0) mx = max(mx, max(I[N-1][hi], D[N-1][hi]));
      |       ^~~~
fish.cpp:4:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |     #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                         ^
fish.cpp:106:7: note: in expansion of macro 'forR'
  106 |       forR(hi, care[N-1].size()) mx = max(mx, E[N-1][hi]);
      |       ^~~~

• 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