oj.uz

Submission #1028098

# Submission time Handle Problem Language Result Execution time Memory
1028098 2024-07-19T13:33:03 Z NeroZein Catfish Farm (IOI22_fish) C++17
78 / 100
 1000 ms 63160 KB 
#include "fish.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int n; 
vector<vector<long long>> nxt;
vector<vector<long long>> pre;
vector<vector<pair<int, int>>> in_col;
vector<vector<vector<long long>>> dp;
 
long long bt(int col, bool f, bool f2) {//is last bigger and does he need payment if he is not
  if (col >= n) {
    return 0;
  }
  long long& ret = dp[col][f][f2];
  if (ret != -1) {
    return ret; 
  }
  ret = 0; 
  int sz = in_col[col].size();
  if (f) {//last is bigger, (he paid for me)
    long long s = 0; 
    for (int i = 0; i < sz; ++i) {
      long long w = s; 
      if (col < n - 1) {
        w += nxt[col][i]; 
      }
      ret = max(ret, bt(col + 1, 1, 0) + w); //I'm bigger than next
      s -= in_col[col][i].second;//delete what I covered 
    }
    //don't build anything..
    ret = max(ret, bt(col + 1, 0, 0));//telling next not to pay for me or take from me
  } else {//last is smaller, I pay for him if f2
    long long s = 0; 
    for (int i = 0; i < sz; ++i) {
      long long w = s;
      if (f2) {
        w += pre[col][i]; 
      }
      ret = max(ret, bt(col + 1, 0, 1) + w); //I'm smaller than next and I need payment (I'll subtract what I cover)
      s -= in_col[col][i].second; 
    }
    long long w = 0;
    if (col < n - 1) {
      w = nxt[col][sz - 1];
    }
    if (f2) {
      w += pre[col][sz - 1]; 
    }
    ret = max(ret, bt(col + 1, 1, 0) + w); //full tower
  }
  //cout << "col, f, f2, ret: " << col << ' ' << f << ' ' << f2 << ' ' << ret << endl; 
  return ret;
}
 
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
  n = N;
  in_col.resize(N);
  for (int i = 0; i < M; ++i) {
    in_col[X[i]].push_back({Y[i], W[i]});
  }
  for (int i = 0; i < N; ++i) {
    sort(in_col[i].begin(), in_col[i].end());
    in_col[i].push_back({N, 0});
  }
  pre.resize(N);
  for (int col = 1; col < N; ++col) {
    pre[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {
      int ptr = 0; 
      long long sum = 0; 
      while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col - 1][ptr].second; 
        ptr++; 
      }
      pre[col][i] = sum; 
    }
  }
  //cout << "PRE: " << pre[1][1] << endl; 
  nxt.resize(N);
  for (int col = 0; col < N - 1; ++col) {
    nxt[col].resize(in_col[col].size());
    for (int i = 0; i < (int) in_col[col].size(); ++i) {
      int ptr = 0;
      long long sum = 0;
      while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
        sum += in_col[col + 1][ptr].second;
        ptr++;
      }
      nxt[col][i] = sum; 
    }
  }
  dp.resize(N);
  for (int i = 0; i < N; ++i) {
    dp[i].resize(2);
    dp[i][0].assign(2, -1);
    dp[i][1].assign(2, -1);
  }
  long long ans = bt(0, 0, 0);
  return ans; 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 42968 KB Output is correct
2 Correct 61 ms 48348 KB Output is correct
3 Correct 36 ms 42576 KB Output is correct
4 Correct 38 ms 42536 KB Output is correct
5 Correct 125 ms 63160 KB Output is correct
6 Correct 127 ms 62804 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1091 ms 15952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42544 KB Output is correct
2 Correct 37 ms 42588 KB Output is correct
3 Correct 48 ms 40532 KB Output is correct
4 Correct 48 ms 44112 KB Output is correct
5 Correct 67 ms 46612 KB Output is correct
6 Correct 60 ms 45908 KB Output is correct
7 Correct 63 ms 46356 KB Output is correct
8 Correct 70 ms 46420 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 21 ms 3548 KB Output is correct
18 Correct 18 ms 3772 KB Output is correct
19 Correct 16 ms 3524 KB Output is correct
20 Correct 15 ms 3676 KB Output is correct
21 Correct 15 ms 3508 KB Output is correct
22 Correct 41 ms 6724 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 10 ms 2648 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 21 ms 3548 KB Output is correct
18 Correct 18 ms 3772 KB Output is correct
19 Correct 16 ms 3524 KB Output is correct
20 Correct 15 ms 3676 KB Output is correct
21 Correct 15 ms 3508 KB Output is correct
22 Correct 41 ms 6724 KB Output is correct
23 Correct 3 ms 1116 KB Output is correct
24 Correct 10 ms 2648 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 2 ms 1628 KB Output is correct
28 Correct 125 ms 15760 KB Output is correct
29 Correct 406 ms 22356 KB Output is correct
30 Correct 96 ms 21844 KB Output is correct
31 Correct 95 ms 21844 KB Output is correct
32 Correct 163 ms 22100 KB Output is correct
33 Correct 109 ms 21852 KB Output is correct
34 Correct 95 ms 21844 KB Output is correct
35 Correct 32 ms 9432 KB Output is correct
36 Correct 122 ms 22512 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42544 KB Output is correct
2 Correct 37 ms 42588 KB Output is correct
3 Correct 48 ms 40532 KB Output is correct
4 Correct 48 ms 44112 KB Output is correct
5 Correct 67 ms 46612 KB Output is correct
6 Correct 60 ms 45908 KB Output is correct
7 Correct 63 ms 46356 KB Output is correct
8 Correct 70 ms 46420 KB Output is correct
9 Correct 63 ms 46160 KB Output is correct
10 Correct 49 ms 26564 KB Output is correct
11 Correct 95 ms 52808 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 38 ms 42452 KB Output is correct
19 Correct 39 ms 42584 KB Output is correct
20 Correct 36 ms 42576 KB Output is correct
21 Correct 42 ms 42576 KB Output is correct
22 Correct 79 ms 47588 KB Output is correct
23 Correct 134 ms 52724 KB Output is correct
24 Correct 104 ms 53316 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 42968 KB Output is correct
2 Correct 61 ms 48348 KB Output is correct
3 Correct 36 ms 42576 KB Output is correct
4 Correct 38 ms 42536 KB Output is correct
5 Correct 125 ms 63160 KB Output is correct
6 Correct 127 ms 62804 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1091 ms 15952 KB Time limit exceeded
9 Halted 0 ms 0 KB -