oj.uz

Submission #625733

# Submission time Handle Problem Language Result Execution time Memory
625733 2022-08-10T17:46:03 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 59880 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define tuple3 tuple<int, int, int>

const int N = 1e5+5, inf = INT_MAX;

int n, m;
map<int, int> w[N];
vi c[N];
map<tuple<int, int, int>, ll> dp; // dp[i][j][k] = maximos peces que puedo conseguir
              // con las k primeras columnas donde
              // en la columna k+1 he subido i-1
              // en la columna k+2 he subido j-1

ll mx(int curr, int h1, int h2) {
  if (curr == -1) return 0;
  
  tuple3 t = make_tuple(curr, h1, h2);
  auto it = dp.find(t);
  if (it != dp.end()) return it->second;
  
  dp[t] = mx(curr-1, 0, h1);
  it = dp.find(t);

  if (curr+1 < n) {
    for (int h : c[curr+1]) {
      h++;
      ll cnt = 0;

      // ver si pillo los de la derecha
      if (curr+1 < n) {
        for (int i = 0; i < h; i++) {
          auto it2 = w[curr+1].find(i);
          if (it2 != w[curr+1].end() && h2-1 < i && h1-1 < i) cnt += it2->second;
        }
      }

      // ver si pillo los de la izquierda
      if (curr-1 >= 0) {
        for (int i = 0; i < h; i++) {
          auto it2 = w[curr-1].find(i);
          if (it2 != w[curr-1].end()) cnt += it2->second;
        }
      }

      // ver si he eliminado alguno de los que he pillado
      for (int i = 0; i < min(h, h1); i++) {
        auto it2 = w[curr].find(i);
        if (it2 != w[curr].end()) cnt -= it2->second;
      }

      it->second = max(it->second, cnt + mx(curr-1, h, h1));
    }
  }

  if (curr-1 >= 0) {
    for (int h : c[curr-1]) {
      h++;
      ll cnt = 0;

      // ver si pillo los de la derecha
      if (curr+1 < n) {
        for (int i = 0; i < h; i++) {
          auto it2 = w[curr+1].find(i);
          if (it2 != w[curr+1].end() && h2-1 < i && h1-1 < i) cnt += it2->second;
        }
      }

      // ver si pillo los de la izquierda
      if (curr-1 >= 0) {
        for (int i = 0; i < h; i++) {
          auto it2 = w[curr-1].find(i);
          if (it2 != w[curr-1].end()) cnt += it2->second;
        }
      }

      // ver si he eliminado alguno de los que he pillado
      for (int i = 0; i < min(h, h1); i++) {
        auto it2 = w[curr].find(i);
        if (it2 != w[curr].end()) cnt -= it2->second;
      }

      it->second = max(it->second, cnt + mx(curr-1, h, h1));
    }
  }
  return it->second;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  n = N;
  m = M;
  for (int i = 0; i < m; i++) {
    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
  return mx(n-1, 0, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 28892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 1087 ms 34876 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 30724 KB Output is correct
2 Correct 56 ms 30808 KB Output is correct
3 Correct 162 ms 44768 KB Output is correct
4 Correct 153 ms 41804 KB Output is correct
5 Correct 399 ms 59880 KB Output is correct
6 Correct 434 ms 59720 KB Output is correct
7 Correct 398 ms 59816 KB Output is correct
8 Correct 406 ms 59856 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7344 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7280 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 9 ms 7636 KB Output is correct
10 Correct 83 ms 9028 KB Output is correct
11 Correct 24 ms 8020 KB Output is correct
12 Correct 32 ms 8392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 15 ms 7892 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7344 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7280 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 9 ms 7636 KB Output is correct
10 Correct 83 ms 9028 KB Output is correct
11 Correct 24 ms 8020 KB Output is correct
12 Correct 32 ms 8392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 15 ms 7892 KB Output is correct
15 Correct 8 ms 7508 KB Output is correct
16 Execution timed out 1090 ms 8728 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7348 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7344 KB Output is correct
5 Correct 3 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7280 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 9 ms 7636 KB Output is correct
10 Correct 83 ms 9028 KB Output is correct
11 Correct 24 ms 8020 KB Output is correct
12 Correct 32 ms 8392 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 15 ms 7892 KB Output is correct
15 Correct 8 ms 7508 KB Output is correct
16 Execution timed out 1090 ms 8728 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 30724 KB Output is correct
2 Correct 56 ms 30808 KB Output is correct
3 Correct 162 ms 44768 KB Output is correct
4 Correct 153 ms 41804 KB Output is correct
5 Correct 399 ms 59880 KB Output is correct
6 Correct 434 ms 59720 KB Output is correct
7 Correct 398 ms 59816 KB Output is correct
8 Correct 406 ms 59856 KB Output is correct
9 Execution timed out 1088 ms 37704 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 28892 KB Time limit exceeded
2 Halted 0 ms 0 KB -