oj.uz

Submission #625759

# Submission time Handle Problem Language Result Execution time Memory
625759 2022-08-10T18:39:54 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 214992 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];
map<int, int> w[N];
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) {
      if (w[i].count(h)) sum3 += w[i][h];
      pre[i][h] = sum3;
 
      if (i-1 >= 0) {
        if (w[i-1].count(h)) sum2 += w[i-1][h];
        pre[i-1][h] = sum2;
      }
      if (i-2 >= 0) {
        if (w[i-2].count(h)) sum1 += w[i-2][h];
        pre[i-2][h] = sum1;
      }
    }
  }

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 72464 KB Output is correct
2 Correct 536 ms 82216 KB Output is correct
3 Correct 33 ms 49556 KB Output is correct
4 Correct 34 ms 49564 KB Output is correct
5 Execution timed out 1098 ms 163612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16724 KB Output is correct
2 Execution timed out 1086 ms 74628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49484 KB Output is correct
2 Correct 35 ms 49484 KB Output is correct
3 Correct 93 ms 66324 KB Output is correct
4 Correct 77 ms 63536 KB Output is correct
5 Correct 157 ms 84736 KB Output is correct
6 Correct 147 ms 84732 KB Output is correct
7 Correct 159 ms 84804 KB Output is correct
8 Correct 173 ms 84888 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16748 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16632 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 11 ms 16620 KB Output is correct
9 Correct 12 ms 16980 KB Output is correct
10 Correct 44 ms 18636 KB Output is correct
11 Correct 20 ms 17436 KB Output is correct
12 Correct 22 ms 17952 KB Output is correct
13 Correct 10 ms 16764 KB Output is correct
14 Correct 16 ms 17464 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16748 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16632 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 11 ms 16620 KB Output is correct
9 Correct 12 ms 16980 KB Output is correct
10 Correct 44 ms 18636 KB Output is correct
11 Correct 20 ms 17436 KB Output is correct
12 Correct 22 ms 17952 KB Output is correct
13 Correct 10 ms 16764 KB Output is correct
14 Correct 16 ms 17464 KB Output is correct
15 Correct 11 ms 17068 KB Output is correct
16 Execution timed out 1082 ms 21304 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16748 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16632 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 11 ms 16620 KB Output is correct
9 Correct 12 ms 16980 KB Output is correct
10 Correct 44 ms 18636 KB Output is correct
11 Correct 20 ms 17436 KB Output is correct
12 Correct 22 ms 17952 KB Output is correct
13 Correct 10 ms 16764 KB Output is correct
14 Correct 16 ms 17464 KB Output is correct
15 Correct 11 ms 17068 KB Output is correct
16 Execution timed out 1082 ms 21304 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49484 KB Output is correct
2 Correct 35 ms 49484 KB Output is correct
3 Correct 93 ms 66324 KB Output is correct
4 Correct 77 ms 63536 KB Output is correct
5 Correct 157 ms 84736 KB Output is correct
6 Correct 147 ms 84732 KB Output is correct
7 Correct 159 ms 84804 KB Output is correct
8 Correct 173 ms 84888 KB Output is correct
9 Correct 279 ms 141156 KB Output is correct
10 Correct 221 ms 73080 KB Output is correct
11 Correct 434 ms 129448 KB Output is correct
12 Correct 8 ms 16724 KB Output is correct
13 Correct 10 ms 16628 KB Output is correct
14 Correct 9 ms 16724 KB Output is correct
15 Correct 11 ms 16668 KB Output is correct
16 Correct 11 ms 16724 KB Output is correct
17 Correct 10 ms 16724 KB Output is correct
18 Correct 35 ms 49552 KB Output is correct
19 Correct 33 ms 49500 KB Output is correct
20 Correct 34 ms 49528 KB Output is correct
21 Correct 58 ms 49592 KB Output is correct
22 Correct 523 ms 139908 KB Output is correct
23 Execution timed out 1094 ms 214992 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 72464 KB Output is correct
2 Correct 536 ms 82216 KB Output is correct
3 Correct 33 ms 49556 KB Output is correct
4 Correct 34 ms 49564 KB Output is correct
5 Execution timed out 1098 ms 163612 KB Time limit exceeded
6 Halted 0 ms 0 KB -