oj.uz

Submission #625753

# Submission time Handle Problem Language Result Execution time Memory
625753 2022-08-10T18:34:31 Z flashmt Catfish Farm (IOI22_fish) C++17
14 / 100
 1000 ms 3992 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
  if (n > 3000)
    return 0;

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++)
      if (make_pair(x[i], y[i]) > make_pair(x[j], y[j]))
      {
        swap(x[i], x[j]);
        swap(y[i], y[j]);
        swap(w[i], w[j]);
      }


  // f: left, g: right
  vector<long long> f(m, -oo), g(m, -oo);
  long long ans = 0;
  for (int i = 0; i < m;)
  {
    int ii = i + 1;
    while (ii < m && x[ii] == x[i])
      ii++;

    for (int j = i; j < ii; j++)
      if (x[j] < n - 1)
      {
        g[j] = w[j];
        for (int jj = 0; jj < i; jj++)
          if (x[jj] == x[j] - 1 && y[jj] >= y[j]) g[j] = max(g[j], f[jj] + w[j]);
          else g[j] = max(g[j], max(f[jj], g[jj]) + w[j]);

        for (int jj = i; jj < j; jj++)
          g[j] = max(g[j], g[jj] + w[j]);
      }

    for (int j = ii - 1; j >= i; j--)
      if (x[j])
      {
        f[j] = w[j];

        for (int jj = 0; jj < i; jj++)
          if (x[jj] + 1 < x[j]) f[j] = max(f[j], max(f[jj], g[jj]) + w[j]);
          else if (y[jj] > y[j]) f[j] = max(f[j], f[jj] + w[j]);

        for (int jj = j + 1; jj < ii; jj++)
          f[j] = max(f[j], f[jj] + w[j]);
      }

    ans = max({ans, f[i], g[i]});
    i = ii;
  }

  return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 47 ms 3992 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 37 ms 340 KB Output is correct
11 Correct 5 ms 212 KB Output is correct
12 Correct 12 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 7 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 27 ms 380 KB Output is correct
17 Execution timed out 1093 ms 1360 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 37 ms 340 KB Output is correct
11 Correct 5 ms 212 KB Output is correct
12 Correct 12 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 7 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 27 ms 380 KB Output is correct
17 Execution timed out 1093 ms 1360 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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