oj.uz

Submission #625761

# Submission time Handle Problem Language Result Execution time Memory
625761 2022-08-10T18:41:02 Z d4xn Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 231520 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) {
      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 244 ms 69320 KB Output is correct
2 Correct 280 ms 79632 KB Output is correct
3 Correct 41 ms 52744 KB Output is correct
4 Correct 41 ms 52684 KB Output is correct
5 Execution timed out 1082 ms 150556 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52684 KB Output is correct
2 Correct 43 ms 52604 KB Output is correct
3 Correct 125 ms 72444 KB Output is correct
4 Correct 99 ms 68428 KB Output is correct
5 Correct 198 ms 94112 KB Output is correct
6 Correct 187 ms 94128 KB Output is correct
7 Correct 206 ms 94156 KB Output is correct
8 Correct 191 ms 94132 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18196 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 13 ms 18628 KB Output is correct
10 Correct 38 ms 20104 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 20 ms 19412 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 18968 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18196 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 13 ms 18628 KB Output is correct
10 Correct 38 ms 20104 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 20 ms 19412 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 18968 KB Output is correct
15 Correct 14 ms 18644 KB Output is correct
16 Execution timed out 1090 ms 26664 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 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18260 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18196 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 13 ms 18628 KB Output is correct
10 Correct 38 ms 20104 KB Output is correct
11 Correct 18 ms 19028 KB Output is correct
12 Correct 20 ms 19412 KB Output is correct
13 Correct 11 ms 18392 KB Output is correct
14 Correct 16 ms 18968 KB Output is correct
15 Correct 14 ms 18644 KB Output is correct
16 Execution timed out 1090 ms 26664 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52684 KB Output is correct
2 Correct 43 ms 52604 KB Output is correct
3 Correct 125 ms 72444 KB Output is correct
4 Correct 99 ms 68428 KB Output is correct
5 Correct 198 ms 94112 KB Output is correct
6 Correct 187 ms 94128 KB Output is correct
7 Correct 206 ms 94156 KB Output is correct
8 Correct 191 ms 94132 KB Output is correct
9 Correct 322 ms 137956 KB Output is correct
10 Correct 215 ms 76212 KB Output is correct
11 Correct 459 ms 134108 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 10 ms 18300 KB Output is correct
14 Correct 10 ms 18300 KB Output is correct
15 Correct 11 ms 18300 KB Output is correct
16 Correct 11 ms 18260 KB Output is correct
17 Correct 11 ms 18232 KB Output is correct
18 Correct 42 ms 52724 KB Output is correct
19 Correct 40 ms 52692 KB Output is correct
20 Correct 41 ms 52620 KB Output is correct
21 Correct 41 ms 52604 KB Output is correct
22 Correct 456 ms 133144 KB Output is correct
23 Correct 937 ms 210136 KB Output is correct
24 Execution timed out 1026 ms 231520 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 69320 KB Output is correct
2 Correct 280 ms 79632 KB Output is correct
3 Correct 41 ms 52744 KB Output is correct
4 Correct 41 ms 52684 KB Output is correct
5 Execution timed out 1082 ms 150556 KB Time limit exceeded
6 Halted 0 ms 0 KB -