oj.uz

Submission #625774

# Submission time Handle Problem Language Result Execution time Memory
625774 2022-08-10T18:57:22 Z d4xn Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 150660 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;
 
  int mxX = 0;
  ll cnt1 = 0;
  ll cnt2 = 0;
  for (int i = 0; i < m; i++) {
    mxX = max(mxX, X[i]);
    if (X[i] == 0) cnt1 += W[i];
    if (X[i] == 1) cnt2 += W[i];

    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  if (mxX <= 1) {
    return max(cnt1, cnt2);
  }

  map<int, int> heights;
  for (int i = 0; i < n; i++) {
    pre[i][-1] = 0;

    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 43 ms 23616 KB Output is correct
2 Correct 58 ms 25636 KB Output is correct
3 Correct 11 ms 18180 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Execution timed out 1104 ms 150660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 18292 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18188 KB Output is correct
2 Correct 54 ms 52720 KB Output is correct
3 Correct 142 ms 72500 KB Output is correct
4 Correct 115 ms 68456 KB Output is correct
5 Correct 221 ms 94236 KB Output is correct
6 Correct 310 ms 94216 KB Output is correct
7 Correct 213 ms 94216 KB Output is correct
8 Correct 219 ms 94136 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 12 ms 18256 KB Output is correct
3 Correct 12 ms 18220 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18296 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 12 ms 18256 KB Output is correct
3 Correct 12 ms 18220 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18296 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 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 12 ms 18256 KB Output is correct
3 Correct 12 ms 18220 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Correct 11 ms 18296 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18188 KB Output is correct
2 Correct 54 ms 52720 KB Output is correct
3 Correct 142 ms 72500 KB Output is correct
4 Correct 115 ms 68456 KB Output is correct
5 Correct 221 ms 94236 KB Output is correct
6 Correct 310 ms 94216 KB Output is correct
7 Correct 213 ms 94216 KB Output is correct
8 Correct 219 ms 94136 KB Output is correct
9 Correct 350 ms 138060 KB Output is correct
10 Correct 232 ms 76188 KB Output is correct
11 Correct 470 ms 134132 KB Output is correct
12 Correct 11 ms 18308 KB Output is correct
13 Correct 13 ms 18304 KB Output is correct
14 Correct 13 ms 18196 KB Output is correct
15 Correct 11 ms 18280 KB Output is correct
16 Incorrect 15 ms 18300 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
17 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23616 KB Output is correct
2 Correct 58 ms 25636 KB Output is correct
3 Correct 11 ms 18180 KB Output is correct
4 Correct 11 ms 18260 KB Output is correct
5 Execution timed out 1104 ms 150660 KB Time limit exceeded
6 Halted 0 ms 0 KB -