oj.uz

Submission #829430

# Submission time Handle Problem Language Result Execution time Memory
829430 2023-08-18T10:35:41 Z erray Catfish Farm (IOI22_fish) C++17
9 / 100
 142 ms 19592 KB 
#include "fish.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/debug.h"
#else 
  #define debug(...) void(37)
#endif

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  vector<int> ord(M);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return pair{X[x], Y[x]} < pair{X[y], Y[y]};
  });
  vector<pair<int, vector<array<int, 2>>>> gs;
  vector<vector<long long>> pref;
  gs.emplace_back(-1, vector<array<int, 2>>{});
  pref.push_back(vector<long long>{0});
  for (int i = 0; i < M; ++i) {
    if (i == 0 || X[ord[i - 1]] != X[ord[i]]) {
      gs.emplace_back(X[ord[i]], vector<array<int, 2>>{});
      pref.push_back(vector<long long>{0});
    }
    gs.back().second.push_back({Y[ord[i]], W[ord[i]]});
    pref.back().push_back(pref.back().back() + W[ord[i]]);
  }
  gs.emplace_back(N, vector<array<int, 2>>{});
  pref.push_back(vector<long long>{0});
  debug(gs, pref);
  const long long inf = (long long) 1e16;
  vector<long long> inc(1, -inf);
  vector<long long> dec(1, -inf);
  vector<long long> valley(1, -inf);
  long long ans = 0;
  for (int i = 1; i < int(gs.size()); ++i) {
    auto& a = gs[i].second;
    //auto& next = gs[i + 1].second;
    auto& prev = gs[i - 1].second;
    int s = int(a.size());
    debug(a, prev);
    //int next_s = int(next.size());
    int prev_s = int(prev.size());
    vector<long long> new_inc(s + 1);
    vector<long long> new_dec(s + 1);
    vector<long long> new_valley(s + 1);
    vector<int> need(s + 1);
    int fop = -1;
    for (int j = 0; j < s; ++j) {
      while (fop + 1 < prev_s && prev[fop + 1][0] <= a[j][0]) {
        ++fop;
      }
      need[j + 1] = fop + 1;
    }
    vector<int> takes(s + 1);
    {
      int p = 0;
      for (int j = 0; j < s; ++j) {
        while (p < prev_s && prev[p][0] < a[j][0]) {
          ++p;
        }
        takes[j] = p;
      }
    }
    takes.back() = prev_s;
    debug(need, takes);
    if (gs[i].first != gs[i - 1].first + 1) {
      long long mx = 0;
      for (auto x : valley) {
        mx = max(mx, x + pref[i - 1].back());
      }
      for (int j = 0; j <= prev_s; ++j) {
        mx = max(mx, pref[i - 1].back() - pref[i - 1][j] + inc[j]);
      }
      ans += mx;
      for (int j = 0; j <= s; ++j) {
        new_valley[j] = 0;
      }
      for (int j = 0; j <= s; ++j) {
        new_dec[j] = pref[i].back() - pref[i][j];
      }
      for (int j = 0; j <= s; ++j) {
        new_inc[j] = 0;
      }
      debug(ans, new_valley, new_dec, new_inc);
    } else {
      //valley case
      {
        int p = prev_s;
        long long mx = -inf;
        for (int j = s; j >= 0; --j) {
          while (p >= need[j]) {
            mx = max(mx, dec[p]);
            --p;
          }
          new_valley[j] = mx;
        }
      } 
      //inc
      {
        {
          long long mx = 0;
          long long val = 0;
          int p = 0;
          for (int j = 0; j <= s; ++j) {
            while (p <= takes[j]) {
              mx = max(mx, inc[p] - pref[i - 1][p]);
              val = max(val, valley[p]);
              ++p;
            }
            new_inc[j] = max(new_inc[j], max(val, mx) + pref[i - 1][takes[j]]); 
          }
        } 
        debug(new_inc);
        {
          long long down = 0;
          for (int j = 0; j <= prev_s; ++j) {
            down = max(down, pref[i - 1][j] + valley[j]);
          }
          for (int j = 0; j <= s; ++j) {
            new_inc[j] = max(new_inc[j], down);
          }
        }
      }
      //dec
      {
        int p = prev_s;
        long long prev_mx = -inf;
        for (int j = s; j >= 0; --j) {
          while (p >= need[j]) {
            prev_mx = max(prev_mx, max(inc[p], dec[p]) + pref[i][j]);
            --p;
          }
          new_dec[j] = max(0LL, prev_mx - pref[i][j]);
        }
      }
      debug(new_valley);
      debug(new_dec);
      debug(new_inc);
    }
    swap(inc, new_inc);
    swap(dec, new_dec);
    swap(valley, new_valley);
  }
  //dont forget the end case 
  debug(ans);
  return ans + dec[0]; 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6200 KB Output is correct
2 Correct 35 ms 7628 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 110 ms 19244 KB Output is correct
6 Correct 142 ms 19592 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 61 ms 11728 KB Output is correct
3 Correct 72 ms 14328 KB Output is correct
4 Correct 27 ms 6232 KB Output is correct
5 Correct 41 ms 7732 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 27 ms 6372 KB Output is correct
13 Correct 35 ms 7628 KB Output is correct
14 Correct 28 ms 6252 KB Output is correct
15 Correct 32 ms 6872 KB Output is correct
16 Correct 36 ms 6272 KB Output is correct
17 Correct 35 ms 6712 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 30 ms 7976 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20850323282256'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 252 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 252 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 252 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 30 ms 7976 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20850323282256'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6200 KB Output is correct
2 Correct 35 ms 7628 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 110 ms 19244 KB Output is correct
6 Correct 142 ms 19592 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 61 ms 11728 KB Output is correct
9 Correct 72 ms 14328 KB Output is correct
10 Correct 27 ms 6232 KB Output is correct
11 Correct 41 ms 7732 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 27 ms 6372 KB Output is correct
19 Correct 35 ms 7628 KB Output is correct
20 Correct 28 ms 6252 KB Output is correct
21 Correct 32 ms 6872 KB Output is correct
22 Correct 36 ms 6272 KB Output is correct
23 Correct 35 ms 6712 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Incorrect 30 ms 7976 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20850323282256'
27 Halted 0 ms 0 KB -