oj.uz

Submission #625827

# Submission time Handle Problem Language Result Execution time Memory
625827 2022-08-10T20:24:18 Z d4xn Catfish Farm (IOI22_fish) C++17
18 / 100
 313 ms 138016 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 (min(h1, h2) > 0) return it->second;

  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;
 
  ll sum = 0;
  bool odd = 0;
  int mxX = 0;
  for (int i = 0; i < m; i++) {
    sum += W[i];
    if (X[i]%2) odd = 1;
    mxX = max(mxX, X[i]);

    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  if (!odd) return sum;
  if (mxX <= 1) {
    ll pre0[n], pre1[n];
    for (int i = 0; i < n; i++) {
      pre0[i] = (i ? pre0[i-1] : 0);
      pre1[i] = (i ? pre1[i-1] : 0);

      auto it = w[0].find(i);
      if (it != w[0].end()) pre0[i] += it->second;


      it = w[1].find(i);
      if (it != w[1].end()) pre1[i] += it->second;
    }

    if (n == 2) return max(pre0[n-1], pre1[n-1]);

    ll ans = max(pre0[n-1], pre1[n-1]);
    for (int i = 0; i < n; i++) {
      ans = max(ans, pre0[i] + pre1[n-1] - pre1[i]);
    }

    if (n >= 3) return ans;
  }

  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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 23636 KB Output is correct
2 Correct 50 ms 25628 KB Output is correct
3 Correct 11 ms 18260 KB Output is correct
4 Correct 12 ms 18260 KB Output is correct
5 Correct 224 ms 40352 KB Output is correct
6 Correct 237 ms 42552 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18224 KB Output is correct
2 Correct 75 ms 30472 KB Output is correct
3 Correct 103 ms 34256 KB Output is correct
4 Correct 39 ms 23700 KB Output is correct
5 Correct 50 ms 25628 KB Output is correct
6 Correct 10 ms 18308 KB Output is correct
7 Correct 12 ms 18260 KB Output is correct
8 Correct 10 ms 18260 KB Output is correct
9 Correct 11 ms 18224 KB Output is correct
10 Correct 10 ms 18224 KB Output is correct
11 Correct 10 ms 18260 KB Output is correct
12 Correct 44 ms 25096 KB Output is correct
13 Correct 64 ms 26980 KB Output is correct
14 Correct 43 ms 25060 KB Output is correct
15 Correct 51 ms 26436 KB Output is correct
16 Correct 45 ms 25132 KB Output is correct
17 Correct 57 ms 26428 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 48 ms 52696 KB Output is correct
3 Correct 127 ms 72568 KB Output is correct
4 Correct 100 ms 68500 KB Output is correct
5 Correct 198 ms 94160 KB Output is correct
6 Correct 189 ms 94208 KB Output is correct
7 Correct 218 ms 94108 KB Output is correct
8 Correct 202 ms 94200 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18260 KB Output is correct
2 Correct 48 ms 52696 KB Output is correct
3 Correct 127 ms 72568 KB Output is correct
4 Correct 100 ms 68500 KB Output is correct
5 Correct 198 ms 94160 KB Output is correct
6 Correct 189 ms 94208 KB Output is correct
7 Correct 218 ms 94108 KB Output is correct
8 Correct 202 ms 94200 KB Output is correct
9 Incorrect 313 ms 138016 KB 1st lines differ - on the 1st token, expected: '99999', found: '74999'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 23636 KB Output is correct
2 Correct 50 ms 25628 KB Output is correct
3 Correct 11 ms 18260 KB Output is correct
4 Correct 12 ms 18260 KB Output is correct
5 Correct 224 ms 40352 KB Output is correct
6 Correct 237 ms 42552 KB Output is correct
7 Correct 10 ms 18224 KB Output is correct
8 Correct 75 ms 30472 KB Output is correct
9 Correct 103 ms 34256 KB Output is correct
10 Correct 39 ms 23700 KB Output is correct
11 Correct 50 ms 25628 KB Output is correct
12 Correct 10 ms 18308 KB Output is correct
13 Correct 12 ms 18260 KB Output is correct
14 Correct 10 ms 18260 KB Output is correct
15 Correct 11 ms 18224 KB Output is correct
16 Correct 10 ms 18224 KB Output is correct
17 Correct 10 ms 18260 KB Output is correct
18 Correct 44 ms 25096 KB Output is correct
19 Correct 64 ms 26980 KB Output is correct
20 Correct 43 ms 25060 KB Output is correct
21 Correct 51 ms 26436 KB Output is correct
22 Correct 45 ms 25132 KB Output is correct
23 Correct 57 ms 26428 KB Output is correct
24 Correct 11 ms 18260 KB Output is correct
25 Correct 48 ms 52696 KB Output is correct
26 Correct 127 ms 72568 KB Output is correct
27 Correct 100 ms 68500 KB Output is correct
28 Correct 198 ms 94160 KB Output is correct
29 Correct 189 ms 94208 KB Output is correct
30 Correct 218 ms 94108 KB Output is correct
31 Correct 202 ms 94200 KB Output is correct
32 Incorrect 10 ms 18260 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
33 Halted 0 ms 0 KB -