oj.uz

Submission #625763

# Submission time Handle Problem Language Result Execution time Memory
625763 2022-08-10T18:43:38 Z d4xn Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 231728 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 tuple2 tuple<int, int>
#define tuple3 tuple<int, int, int>
 
const int N = 1e5;
 
int n, m;
vi c[N];
unordered_map<int, int> w[N];
unordered_map<int, ll> pre[N];
map<tuple2, ll> dp[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;
  
  tuple2 t = make_tuple(h1, h2);
  auto it = dp[curr].find(t);
  if (it != dp[curr].end()) return it->second;
  
  dp[curr][t] = mx(curr-1, 0, h1);
  it = dp[curr].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 && h > max(h1, h2)) {
        if (curr+2 == n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(h1-1));
        }
        else {
          cnt += pre[curr+1][h-1] - pre[curr+1][max(h1, h2)-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(max(h1, h2)-1));
        }
      }
 
      // ver si pillo los de la izquierda      
      if (curr-1 >= 0) {
        cnt += pre[curr-1][h-1];
        //assert(pre[curr-1].count(h-1));
      }
      
 
      // ver si he eliminado alguno de los que he pillado
      cnt -= pre[curr][min(h, h1)-1];
      //assert(pre[curr].count(min(h, h1)-1));
 
      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 && h > max(h1, h2)) {
        if (curr+2 == n) {
          cnt += pre[curr+1][h-1] - pre[curr+1][h1-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(h1-1));
        }
        else {
          cnt += pre[curr+1][h-1] - pre[curr+1][max(h1, h2)-1];
          //assert(pre[curr+1].count(h-1) && pre[curr+1].count(max(h1, h2)-1));
        }
      }
 
      // ver si pillo los de la izquierda      
      if (curr-1 >= 0) {
        cnt += pre[curr-1][h-1];
        //assert(pre[curr-1].count(h-1));
      }
      
 
      // ver si he eliminado alguno de los que he pillado
      cnt -= pre[curr][min(h, h1)-1];
      //assert(pre[curr].count(min(h, h1)-1));
 
      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]);
  }
 
  map<int, int> heights;
  for (int i = 0; i < n; i++) {
    pre[i][-1] = 0;

    //sort(c[i].begin(), c[i].end());
    for (int &h : c[i]) heights[h]++;
 
    if (i >= 3) {
      for (int &h : c[i-3]) {
        heights[h]--;
        if (!heights[h]) heights.erase(h);
      }
    }
 
    ll sum1 = 0;
    ll sum2 = 0;
    ll sum3 = 0;
    for (auto &[h, cnt] : heights) {
      auto it = w[i].find(h);
      if (it != w[i].end()) sum3 += it->second;
      pre[i][h] = sum3;
 
      if (i-1 >= 0) {
        it = w[i-1].find(h);
        if (it != w[i-1].end()) sum2 += it->second;
        pre[i-1][h] = sum2;
      }
      if (i-2 >= 0) {
        it = w[i-2].find(h);
        if (it != w[i-2].end()) sum1 += it->second;
        pre[i-2][h] = sum1;
      }
    }
  }

  return mx(n-1, 0, 0);
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 69332 KB Output is correct
2 Correct 288 ms 79644 KB Output is correct
3 Correct 41 ms 52628 KB Output is correct
4 Correct 41 ms 52652 KB Output is correct
5 Execution timed out 1093 ms 150580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18260 KB Output is correct
2 Execution timed out 1095 ms 70432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 52692 KB Output is correct
2 Correct 41 ms 52628 KB Output is correct
3 Correct 117 ms 72420 KB Output is correct
4 Correct 104 ms 68428 KB Output is correct
5 Correct 195 ms 94220 KB Output is correct
6 Correct 203 ms 94128 KB Output is correct
7 Correct 185 ms 94224 KB Output is correct
8 Correct 190 ms 94116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18304 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 12 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18260 KB Output is correct
6 Correct 11 ms 18264 KB Output is correct
7 Correct 11 ms 18304 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 14 ms 18648 KB Output is correct
10 Correct 44 ms 20008 KB Output is correct
11 Correct 18 ms 18948 KB Output is correct
12 Correct 21 ms 19412 KB Output is correct
13 Correct 11 ms 18376 KB Output is correct
14 Correct 18 ms 18988 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18304 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 12 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18260 KB Output is correct
6 Correct 11 ms 18264 KB Output is correct
7 Correct 11 ms 18304 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 14 ms 18648 KB Output is correct
10 Correct 44 ms 20008 KB Output is correct
11 Correct 18 ms 18948 KB Output is correct
12 Correct 21 ms 19412 KB Output is correct
13 Correct 11 ms 18376 KB Output is correct
14 Correct 18 ms 18988 KB Output is correct
15 Correct 12 ms 18660 KB Output is correct
16 Execution timed out 1092 ms 26356 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18304 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 12 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18260 KB Output is correct
6 Correct 11 ms 18264 KB Output is correct
7 Correct 11 ms 18304 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 14 ms 18648 KB Output is correct
10 Correct 44 ms 20008 KB Output is correct
11 Correct 18 ms 18948 KB Output is correct
12 Correct 21 ms 19412 KB Output is correct
13 Correct 11 ms 18376 KB Output is correct
14 Correct 18 ms 18988 KB Output is correct
15 Correct 12 ms 18660 KB Output is correct
16 Execution timed out 1092 ms 26356 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 52692 KB Output is correct
2 Correct 41 ms 52628 KB Output is correct
3 Correct 117 ms 72420 KB Output is correct
4 Correct 104 ms 68428 KB Output is correct
5 Correct 195 ms 94220 KB Output is correct
6 Correct 203 ms 94128 KB Output is correct
7 Correct 185 ms 94224 KB Output is correct
8 Correct 190 ms 94116 KB Output is correct
9 Correct 337 ms 138048 KB Output is correct
10 Correct 208 ms 76172 KB Output is correct
11 Correct 469 ms 134060 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 11 ms 18200 KB Output is correct
14 Correct 11 ms 18260 KB Output is correct
15 Correct 11 ms 18260 KB Output is correct
16 Correct 10 ms 18304 KB Output is correct
17 Correct 10 ms 18296 KB Output is correct
18 Correct 40 ms 52712 KB Output is correct
19 Correct 41 ms 52684 KB Output is correct
20 Correct 41 ms 52632 KB Output is correct
21 Correct 40 ms 52724 KB Output is correct
22 Correct 448 ms 133212 KB Output is correct
23 Correct 894 ms 210124 KB Output is correct
24 Correct 936 ms 231728 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 69332 KB Output is correct
2 Correct 288 ms 79644 KB Output is correct
3 Correct 41 ms 52628 KB Output is correct
4 Correct 41 ms 52652 KB Output is correct
5 Execution timed out 1093 ms 150580 KB Time limit exceeded
6 Halted 0 ms 0 KB -