oj.uz

답안 #626641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626641 2022-08-11T15:25:21 Z d4xn 메기 농장 (IOI22_fish) C++17
23 / 100
 1000 ms 124720 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];
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++) {
    ll sum = 0;
    for (auto &[h, we] : w[i]) {
      sum += we;
      pre[i][h] = sum;
    }
    pre[i][-1] = 0;
  }

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

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 75124 KB Output is correct
2 Correct 227 ms 82644 KB Output is correct
3 Correct 54 ms 64460 KB Output is correct
4 Correct 51 ms 64404 KB Output is correct
5 Execution timed out 1082 ms 109060 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28372 KB Output is correct
2 Execution timed out 1084 ms 70428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 64432 KB Output is correct
2 Correct 53 ms 64468 KB Output is correct
3 Correct 148 ms 93872 KB Output is correct
4 Correct 144 ms 90372 KB Output is correct
5 Correct 232 ms 115280 KB Output is correct
6 Correct 211 ms 115236 KB Output is correct
7 Correct 230 ms 115292 KB Output is correct
8 Correct 220 ms 115308 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28372 KB Output is correct
2 Correct 17 ms 28468 KB Output is correct
3 Correct 18 ms 28408 KB Output is correct
4 Correct 19 ms 28428 KB Output is correct
5 Correct 19 ms 28372 KB Output is correct
6 Correct 19 ms 28372 KB Output is correct
7 Correct 17 ms 28476 KB Output is correct
8 Correct 17 ms 28480 KB Output is correct
9 Correct 17 ms 28608 KB Output is correct
10 Correct 24 ms 29200 KB Output is correct
11 Correct 20 ms 28756 KB Output is correct
12 Correct 21 ms 28912 KB Output is correct
13 Correct 20 ms 28500 KB Output is correct
14 Correct 19 ms 28884 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28372 KB Output is correct
2 Correct 17 ms 28468 KB Output is correct
3 Correct 18 ms 28408 KB Output is correct
4 Correct 19 ms 28428 KB Output is correct
5 Correct 19 ms 28372 KB Output is correct
6 Correct 19 ms 28372 KB Output is correct
7 Correct 17 ms 28476 KB Output is correct
8 Correct 17 ms 28480 KB Output is correct
9 Correct 17 ms 28608 KB Output is correct
10 Correct 24 ms 29200 KB Output is correct
11 Correct 20 ms 28756 KB Output is correct
12 Correct 21 ms 28912 KB Output is correct
13 Correct 20 ms 28500 KB Output is correct
14 Correct 19 ms 28884 KB Output is correct
15 Correct 17 ms 28756 KB Output is correct
16 Correct 66 ms 29096 KB Output is correct
17 Execution timed out 1092 ms 36260 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28372 KB Output is correct
2 Correct 17 ms 28468 KB Output is correct
3 Correct 18 ms 28408 KB Output is correct
4 Correct 19 ms 28428 KB Output is correct
5 Correct 19 ms 28372 KB Output is correct
6 Correct 19 ms 28372 KB Output is correct
7 Correct 17 ms 28476 KB Output is correct
8 Correct 17 ms 28480 KB Output is correct
9 Correct 17 ms 28608 KB Output is correct
10 Correct 24 ms 29200 KB Output is correct
11 Correct 20 ms 28756 KB Output is correct
12 Correct 21 ms 28912 KB Output is correct
13 Correct 20 ms 28500 KB Output is correct
14 Correct 19 ms 28884 KB Output is correct
15 Correct 17 ms 28756 KB Output is correct
16 Correct 66 ms 29096 KB Output is correct
17 Execution timed out 1092 ms 36260 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 64432 KB Output is correct
2 Correct 53 ms 64468 KB Output is correct
3 Correct 148 ms 93872 KB Output is correct
4 Correct 144 ms 90372 KB Output is correct
5 Correct 232 ms 115280 KB Output is correct
6 Correct 211 ms 115236 KB Output is correct
7 Correct 230 ms 115292 KB Output is correct
8 Correct 220 ms 115308 KB Output is correct
9 Correct 254 ms 124720 KB Output is correct
10 Incorrect 207 ms 83252 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36454254938101'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 75124 KB Output is correct
2 Correct 227 ms 82644 KB Output is correct
3 Correct 54 ms 64460 KB Output is correct
4 Correct 51 ms 64404 KB Output is correct
5 Execution timed out 1082 ms 109060 KB Time limit exceeded
6 Halted 0 ms 0 KB -