oj.uz

답안 #625785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625785 2022-08-10T19:10:09 Z d4xn 메기 농장 (IOI22_fish) C++17
9 / 100
 1000 ms 150588 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;
  for (int i = 0; i < m; i++) {
    mxX = max(mxX, X[i]);

    w[X[i]][Y[i]] = W[i];
    c[X[i]].push_back(Y[i]);
  }
 
  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);
      if (w[0].count(i)) pre0[i] += w[0][i];
      if (w[1].count(i)) pre1[i] += w[1][i];
    }

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 25044 KB Output is correct
2 Correct 54 ms 27000 KB Output is correct
3 Correct 13 ms 19796 KB Output is correct
4 Correct 12 ms 19796 KB Output is correct
5 Execution timed out 1081 ms 150588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 18260 KB Output is correct
2 Correct 83 ms 30472 KB Output is correct
3 Incorrect 101 ms 34328 KB 1st lines differ - on the 1st token, expected: '50032678213482', found: '50049263855627'
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19800 KB Output is correct
2 Correct 56 ms 52684 KB Output is correct
3 Correct 135 ms 72436 KB Output is correct
4 Correct 108 ms 68540 KB Output is correct
5 Correct 214 ms 94156 KB Output is correct
6 Correct 239 ms 94256 KB Output is correct
7 Correct 219 ms 94236 KB Output is correct
8 Correct 219 ms 94152 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18248 KB Output is correct
3 Incorrect 13 ms 18296 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18248 KB Output is correct
3 Incorrect 13 ms 18296 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18248 KB Output is correct
3 Incorrect 13 ms 18296 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19800 KB Output is correct
2 Correct 56 ms 52684 KB Output is correct
3 Correct 135 ms 72436 KB Output is correct
4 Correct 108 ms 68540 KB Output is correct
5 Correct 214 ms 94156 KB Output is correct
6 Correct 239 ms 94256 KB Output is correct
7 Correct 219 ms 94236 KB Output is correct
8 Correct 219 ms 94152 KB Output is correct
9 Correct 364 ms 137940 KB Output is correct
10 Correct 240 ms 76112 KB Output is correct
11 Correct 519 ms 134068 KB Output is correct
12 Incorrect 11 ms 18260 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 25044 KB Output is correct
2 Correct 54 ms 27000 KB Output is correct
3 Correct 13 ms 19796 KB Output is correct
4 Correct 12 ms 19796 KB Output is correct
5 Execution timed out 1081 ms 150588 KB Time limit exceeded
6 Halted 0 ms 0 KB -