oj.uz

Submission #643981

# Submission time Handle Problem Language Result Execution time Memory
643981 2022-09-23T11:35:32 Z NintsiChkhaidze Catfish Farm (IOI22_fish) C++17
35 / 100
 246 ms 24096 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 1005;
ll p[N][N],dp[N][N][5],suff[N][N];
 
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
 
  for (int i = 0;i < m; i++){
    X[i]++,Y[i]++;
    p[X[i]][Y[i]] += W[i];
  }
 
  for (int j = 1; j <= n; j++)
    for (int i = 1; i <= n; i++)
      p[j][i] += p[j][i - 1];
 
  for (int j = 1; j <= n; j++){
    for (int a = 0; a <= n; a++){
      
      //update dp[j][a][0]
      for (int b = a; b <= n; b++){
        // ll v = max(dp[j - 1][b][0],dp[j - 1][b][1]) + p[j][b];
        ll v = suff[j - 1][b];
        
        dp[j][a][0] = max(dp[j][a][0], v - p[j][a]);
      }
 
      //update dp[j][a][1]
      for (int b = 0; b <= a; b++){
        ll v = dp[j - 1][b][1] - p[j - 1][b];
        //v = pref[j - 1][b]
        
        dp[j][a][1] = max(dp[j][a][1], v + p[j - 1][a]);
      }
      
      //c 0 a
      if (j >= 3){
        for (int c = 0; c <= n; c++){
          ll v = max(dp[j - 2][c][0],dp[j - 2][c][1]);
          dp[j][a][1] = max(dp[j][a][1], v + p[j - 1][max(a,c)]);
        }
      }
      
    }

    for (int a = n; a >= 0; a--)
        suff[j][a] = max(suff[j][a+1],max(dp[j][a][0],dp[j][a][1]) + p[j + 1][a]);
  }
 
  ll ans = 0;
  for (int a = 0; a <= n; a++)
      ans=max(ans,max(dp[n][a][0],dp[n][a][1]));
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 20248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 246 ms 24096 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 16332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
10 Correct 84 ms 8876 KB Output is correct
11 Correct 11 ms 3284 KB Output is correct
12 Correct 78 ms 8800 KB Output is correct
13 Correct 2 ms 1492 KB Output is correct
14 Correct 79 ms 8804 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
10 Correct 84 ms 8876 KB Output is correct
11 Correct 11 ms 3284 KB Output is correct
12 Correct 78 ms 8800 KB Output is correct
13 Correct 2 ms 1492 KB Output is correct
14 Correct 79 ms 8804 KB Output is correct
15 Correct 80 ms 8816 KB Output is correct
16 Correct 3 ms 1492 KB Output is correct
17 Correct 91 ms 9996 KB Output is correct
18 Correct 92 ms 9956 KB Output is correct
19 Correct 91 ms 10024 KB Output is correct
20 Correct 92 ms 9972 KB Output is correct
21 Correct 92 ms 10028 KB Output is correct
22 Correct 103 ms 10992 KB Output is correct
23 Correct 80 ms 9048 KB Output is correct
24 Correct 85 ms 9580 KB Output is correct
25 Correct 91 ms 8832 KB Output is correct
26 Correct 80 ms 9036 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
10 Correct 84 ms 8876 KB Output is correct
11 Correct 11 ms 3284 KB Output is correct
12 Correct 78 ms 8800 KB Output is correct
13 Correct 2 ms 1492 KB Output is correct
14 Correct 79 ms 8804 KB Output is correct
15 Correct 80 ms 8816 KB Output is correct
16 Correct 3 ms 1492 KB Output is correct
17 Correct 91 ms 9996 KB Output is correct
18 Correct 92 ms 9956 KB Output is correct
19 Correct 91 ms 10024 KB Output is correct
20 Correct 92 ms 9972 KB Output is correct
21 Correct 92 ms 10028 KB Output is correct
22 Correct 103 ms 10992 KB Output is correct
23 Correct 80 ms 9048 KB Output is correct
24 Correct 85 ms 9580 KB Output is correct
25 Correct 91 ms 8832 KB Output is correct
26 Correct 80 ms 9036 KB Output is correct
27 Runtime error 2 ms 596 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 16332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 20248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -