oj.uz

Submission #838847

# Submission time Handle Problem Language Result Execution time Memory
838847 2023-08-27T23:05:12 Z taher Catfish Farm (IOI22_fish) C++17
9 / 100
 225 ms 113804 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
  vector<vector<int>> at(n);
  vector<vector<int>> ids(n);
  for (int i = 0; i < m; i++) {
    at[x[i]].push_back(y[i]); 
    ids[x[i]].push_back(i);
  }
  
  
  for (int i = 0; i < n; i++) {
    sort(ids[i].begin(), ids[i].end(), [&](int a, int b) {
      return at[i][a] < at[i][b];    
    });
    sort(at[i].begin(), at[i].end()); 
  }
  
  vector<vector<long long>> pref(n);
  for (int i = 0; i < n; i++) {
    if (at[i].empty()) {
      continue; 
    }
    pref[i].resize((int) at[i].size());
    pref[i][0] = w[ids[i][0]];
    for (int j = 1; j < (int) at[i].size(); j++) {
      pref[i][j] = pref[i][j - 1] + w[ids[i][j]];
    }
  }
  
  vector<vector<int>> endpoints(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      for (auto v : at[i - 1]) {
        endpoints[i].push_back(v); 
      } 
    }
    if (i < n - 1) {
      for (auto v : at[i + 1]) {
        endpoints[i].push_back(v); 
      }            
    }
    endpoints[i].push_back(-1);
    
    sort(endpoints[i].begin(), endpoints[i].end());
    endpoints[i].erase(unique(endpoints[i].begin(), endpoints[i].end()), endpoints[i].end());
  }
  
  int current = 0;
  vector<vector<int>> coords(n);
  for (int i = 0; i < n; i++) {
    coords[i].resize((int) endpoints[i].size());
    for (int j = 0; j < (int) endpoints[i].size(); j++) {
      coords[i][j] = current++; 
    }
  }  
  
  auto Count = [&](int col, int from, int to) {
    int xx = upper_bound(at[col].begin(), at[col].end(), from) - at[col].begin();
    int yy = upper_bound(at[col].begin(), at[col].end(), to) - at[col].begin();
    yy--;
    
    if (xx <= yy) {
      assert(yy < (int) at[col].size());
      long long s = pref[col][yy];
      if (xx > 0) {
        s -= pref[col][xx - 1]; 
      }
      return s;        
    }
    return 0LL;
  };
  
  /*
    0: undef
    1: increasing
    2: decreasing
  */
  
  vector<vector<vector<long long>>> dp(current, vector<vector<long long>> (3, vector<long long> (2, -1)));
  
  function<long long(int, int, int, int)> DP = [&](int col, int id, int state, int used_dec) {
    // need to assign a number between 0 and m-1 to (col, id) though
    
    if (dp[coords[col][id]][state][used_dec] != -1) {
      return dp[coords[col][id]][state][used_dec]; 
    }
    
    long long ans = 0;
    int current_height = endpoints[col][id];
    if (state == 1) {
      if (id + 1 < (int) endpoints[col].size()) {
        long long cnt = Count(col - 1, current_height, endpoints[col][id + 1]);
        ans = max(ans, DP(col, id + 1, 1, used_dec) + cnt); 
      }      
    } else if (state == 2) {
      if (id - 1 > 0) {
        long long cnt = Count(col, endpoints[col][id - 1], current_height);
        ans = max(ans, DP(col, id - 1, 2, used_dec) + cnt);
      } 
    } else {
      if (id + 1 < (int) endpoints[col].size()) {
        ans = max(ans, DP(col, id + 1, 0, used_dec)); 
      }
    }
    
    if (col + 1 < n) {
      if (!used_dec) {
        int nid = lower_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
        if (nid < (int) endpoints[col + 1].size()) {
          ans = max(ans, DP(col + 1, nid, 1, used_dec) + Count(col, current_height, endpoints[col + 1][nid])); 
        }
      }
      int nid = upper_bound(endpoints[col + 1].begin(), endpoints[col + 1].end(), current_height) - endpoints[col + 1].begin();
      --nid;
      if (nid > 0) {
        ans = max(ans, DP(col + 1, nid, 2, 1) + Count(col + 1, endpoints[col + 1][nid], current_height));
      }
      
      ans = max(ans, Count(col + 1, -1, current_height));
    }
    if (col + 2 < n) {
      int nid = lower_bound(endpoints[col + 2].begin(), endpoints[col + 2].end(), current_height) - endpoints[col + 2].begin();
      if (nid < (int) endpoints[col + 2].size()) {
        ans = max(ans, DP(col + 2, nid, 1, 0) + Count(col + 1, -1, endpoints[col + 2][nid]));
      }
      nid = 0;
      ans = max(ans, DP(col + 2, nid, 0, 0) + Count(col + 1, -1, current_height));
    }
    return dp[coords[col][id]][state][used_dec] = ans;
  };
  
  long long res = DP(0, 0, 0, 0);
  return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 96416 KB Output is correct
2 Correct 147 ms 112192 KB Output is correct
3 Correct 73 ms 62868 KB Output is correct
4 Correct 61 ms 62848 KB Output is correct
5 Runtime error 80 ms 29124 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 47 ms 19572 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 62932 KB Output is correct
2 Correct 58 ms 62800 KB Output is correct
3 Correct 123 ms 74060 KB Output is correct
4 Correct 105 ms 73904 KB Output is correct
5 Correct 184 ms 94228 KB Output is correct
6 Correct 177 ms 94132 KB Output is correct
7 Correct 183 ms 94184 KB Output is correct
8 Correct 183 ms 94156 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 260 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 212 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 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216813918028'
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 1 ms 260 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 212 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 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216813918028'
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 1 ms 260 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 212 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 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216813918028'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 62932 KB Output is correct
2 Correct 58 ms 62800 KB Output is correct
3 Correct 123 ms 74060 KB Output is correct
4 Correct 105 ms 73904 KB Output is correct
5 Correct 184 ms 94228 KB Output is correct
6 Correct 177 ms 94132 KB Output is correct
7 Correct 183 ms 94184 KB Output is correct
8 Correct 183 ms 94156 KB Output is correct
9 Correct 225 ms 113804 KB Output is correct
10 Runtime error 37 ms 16184 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 96416 KB Output is correct
2 Correct 147 ms 112192 KB Output is correct
3 Correct 73 ms 62868 KB Output is correct
4 Correct 61 ms 62848 KB Output is correct
5 Runtime error 80 ms 29124 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -