oj.uz

Submission #626645

# Submission time Handle Problem Language Result Execution time Memory
626645 2022-08-11T15:27:30 Z d4xn Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 161508 KB 
#pragma GCC optimize ("Ofast")
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
#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];
map<int, ll> pre[N];
unordered_map<int, ll> dp[3][N];
 
ll preS(int col, int x) {
  auto it = pre[col].upper_bound(x);
  if (it == pre[col].begin()) return 0;
  return (--it)->second;
}

ll mx(int curr, int h1, int state) {
  if (curr == -1) return 0;
  
  auto it = dp[state][curr].find(h1);
  if (it != dp[state][curr].end()) return it->second;
  
  if (state != 2) dp[state][curr][h1] = mx(curr-1, h1, 2);
  else dp[state][curr][h1] = mx(curr-1, 0, 1);
  it = dp[state][curr].find(h1);

  if (!state) {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        if (h >= h1) break;

        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }
  
        // ver si he eliminado alguno de los que he pillado
        cnt -= preS(curr, h-1);
  
        it->second = max(it->second, cnt + mx(curr-1, h, 0));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        if (h >= h1) break;

        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }
  
        // ver si he eliminado alguno de los que he pillado
        cnt -= preS(curr, h-1);
  
        it->second = max(it->second, cnt + mx(curr-1, h, 0));
      }
    }
  }
  else if (state == 1) {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }

        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += preS(curr+1, h-1) - preS(curr+1, h1-1);
        }
        
        // ver si he eliminado alguno de los que he pillado
        cnt -= preS(curr, min(h, h1)-1);
  
        if (h <= h1) it->second = max(it->second, cnt + mx(curr-1, h, 0));
        else it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }

        // ver si pillo los de la derecha      
        if (h > h1 && curr+1 < n) {
          cnt += preS(curr+1, h-1) - preS(curr+1, h1-1);
        }
        
        // ver si he eliminado alguno de los que he pillado
        cnt -= preS(curr, min(h, h1)-1);
  
        if (h <= h1) it->second = max(it->second, cnt + mx(curr-1, h, 0));
        else it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  }
  else {
    if (curr+1 < n) {
      for (int h : c[curr+1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }

        // ver si pillo los de la derecha
        if (h > h1 && curr+1 < n) {
          cnt += preS(curr+1, h-1) - preS(curr+1, h1-1);
        }
  
        it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  
    if (curr-1 >= 0) {
      for (int h : c[curr-1]) {
        h++;
        ll cnt = 0;
  
        // ver si pillo los de la izquierda      
        if (curr-1 >= 0) {
          cnt += preS(curr-1, h-1);
        }

        // ver si pillo los de la derecha
        if (h > h1 && curr+1 < n) {
          cnt += preS(curr+1, h-1) - preS(curr+1, h1-1);
        }
  
        it->second = max(it->second, cnt + mx(curr-1, h, 1));
      }
    }
  }

  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++) {
    c[X[i]].push_back(Y[i]);
    w[X[i]][Y[i]] = W[i];
  }

  for (int i = 0; i < n; i++) {
    sort(c[i].begin(), c[i].end());
    ll sum = 0;
    for (int &h : c[i]) {
      sum += w[i][h];
      pre[i][h] = sum;
    }
    pre[i][-1] = 0;
  }

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 75248 KB Output is correct
2 Correct 137 ms 83128 KB Output is correct
3 Correct 50 ms 65220 KB Output is correct
4 Correct 53 ms 65356 KB Output is correct
5 Execution timed out 1095 ms 110264 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29268 KB Output is correct
2 Execution timed out 1097 ms 69964 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 65224 KB Output is correct
2 Correct 52 ms 65140 KB Output is correct
3 Correct 167 ms 99672 KB Output is correct
4 Correct 126 ms 94412 KB Output is correct
5 Correct 236 ms 125428 KB Output is correct
6 Correct 280 ms 125480 KB Output is correct
7 Correct 241 ms 125412 KB Output is correct
8 Correct 266 ms 125516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29188 KB Output is correct
2 Correct 18 ms 29276 KB Output is correct
3 Correct 17 ms 29140 KB Output is correct
4 Correct 19 ms 29268 KB Output is correct
5 Correct 17 ms 29268 KB Output is correct
6 Correct 17 ms 29268 KB Output is correct
7 Correct 17 ms 29256 KB Output is correct
8 Correct 17 ms 29184 KB Output is correct
9 Correct 17 ms 29440 KB Output is correct
10 Correct 26 ms 29908 KB Output is correct
11 Correct 20 ms 29468 KB Output is correct
12 Correct 21 ms 29692 KB Output is correct
13 Correct 18 ms 29256 KB Output is correct
14 Correct 19 ms 29624 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29188 KB Output is correct
2 Correct 18 ms 29276 KB Output is correct
3 Correct 17 ms 29140 KB Output is correct
4 Correct 19 ms 29268 KB Output is correct
5 Correct 17 ms 29268 KB Output is correct
6 Correct 17 ms 29268 KB Output is correct
7 Correct 17 ms 29256 KB Output is correct
8 Correct 17 ms 29184 KB Output is correct
9 Correct 17 ms 29440 KB Output is correct
10 Correct 26 ms 29908 KB Output is correct
11 Correct 20 ms 29468 KB Output is correct
12 Correct 21 ms 29692 KB Output is correct
13 Correct 18 ms 29256 KB Output is correct
14 Correct 19 ms 29624 KB Output is correct
15 Correct 17 ms 29504 KB Output is correct
16 Correct 67 ms 29864 KB Output is correct
17 Execution timed out 1071 ms 36928 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29188 KB Output is correct
2 Correct 18 ms 29276 KB Output is correct
3 Correct 17 ms 29140 KB Output is correct
4 Correct 19 ms 29268 KB Output is correct
5 Correct 17 ms 29268 KB Output is correct
6 Correct 17 ms 29268 KB Output is correct
7 Correct 17 ms 29256 KB Output is correct
8 Correct 17 ms 29184 KB Output is correct
9 Correct 17 ms 29440 KB Output is correct
10 Correct 26 ms 29908 KB Output is correct
11 Correct 20 ms 29468 KB Output is correct
12 Correct 21 ms 29692 KB Output is correct
13 Correct 18 ms 29256 KB Output is correct
14 Correct 19 ms 29624 KB Output is correct
15 Correct 17 ms 29504 KB Output is correct
16 Correct 67 ms 29864 KB Output is correct
17 Execution timed out 1071 ms 36928 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 65224 KB Output is correct
2 Correct 52 ms 65140 KB Output is correct
3 Correct 167 ms 99672 KB Output is correct
4 Correct 126 ms 94412 KB Output is correct
5 Correct 236 ms 125428 KB Output is correct
6 Correct 280 ms 125480 KB Output is correct
7 Correct 241 ms 125412 KB Output is correct
8 Correct 266 ms 125516 KB Output is correct
9 Correct 326 ms 134876 KB Output is correct
10 Correct 207 ms 87932 KB Output is correct
11 Correct 419 ms 146684 KB Output is correct
12 Correct 16 ms 29140 KB Output is correct
13 Correct 21 ms 29264 KB Output is correct
14 Correct 21 ms 29152 KB Output is correct
15 Correct 18 ms 29168 KB Output is correct
16 Correct 19 ms 29268 KB Output is correct
17 Correct 21 ms 29180 KB Output is correct
18 Correct 50 ms 65252 KB Output is correct
19 Correct 66 ms 65244 KB Output is correct
20 Correct 59 ms 65236 KB Output is correct
21 Correct 72 ms 65252 KB Output is correct
22 Correct 313 ms 123500 KB Output is correct
23 Correct 510 ms 158748 KB Output is correct
24 Correct 511 ms 161508 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 75248 KB Output is correct
2 Correct 137 ms 83128 KB Output is correct
3 Correct 50 ms 65220 KB Output is correct
4 Correct 53 ms 65356 KB Output is correct
5 Execution timed out 1095 ms 110264 KB Time limit exceeded
6 Halted 0 ms 0 KB -