oj.uz

Submission #625737

# Submission time Handle Problem Language Result Execution time Memory
625737 2022-08-10T17:50:41 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 58212 KB 
#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#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 1100 ms 27444 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 1083 ms 33448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29132 KB Output is correct
2 Correct 49 ms 29220 KB Output is correct
3 Correct 161 ms 43288 KB Output is correct
4 Correct 156 ms 40060 KB Output is correct
5 Correct 406 ms 58120 KB Output is correct
6 Correct 403 ms 58152 KB Output is correct
7 Correct 418 ms 58104 KB Output is correct
8 Correct 406 ms 58212 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 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 10 ms 7648 KB Output is correct
10 Correct 76 ms 9024 KB Output is correct
11 Correct 25 ms 8016 KB Output is correct
12 Correct 28 ms 8328 KB Output is correct
13 Correct 5 ms 7380 KB Output is correct
14 Correct 15 ms 7928 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 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 10 ms 7648 KB Output is correct
10 Correct 76 ms 9024 KB Output is correct
11 Correct 25 ms 8016 KB Output is correct
12 Correct 28 ms 8328 KB Output is correct
13 Correct 5 ms 7380 KB Output is correct
14 Correct 15 ms 7928 KB Output is correct
15 Correct 9 ms 7508 KB Output is correct
16 Execution timed out 1087 ms 8668 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 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 7 ms 7252 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 10 ms 7648 KB Output is correct
10 Correct 76 ms 9024 KB Output is correct
11 Correct 25 ms 8016 KB Output is correct
12 Correct 28 ms 8328 KB Output is correct
13 Correct 5 ms 7380 KB Output is correct
14 Correct 15 ms 7928 KB Output is correct
15 Correct 9 ms 7508 KB Output is correct
16 Execution timed out 1087 ms 8668 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29132 KB Output is correct
2 Correct 49 ms 29220 KB Output is correct
3 Correct 161 ms 43288 KB Output is correct
4 Correct 156 ms 40060 KB Output is correct
5 Correct 406 ms 58120 KB Output is correct
6 Correct 403 ms 58152 KB Output is correct
7 Correct 418 ms 58104 KB Output is correct
8 Correct 406 ms 58212 KB Output is correct
9 Execution timed out 1081 ms 35936 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 1100 ms 27444 KB Time limit exceeded
2 Halted 0 ms 0 KB -