oj.uz

Submission #643983

# Submission time Handle Problem Language Result Execution time Memory
643983 2022-09-23T11:41:14 Z NintsiChkhaidze Catfish Farm (IOI22_fish) C++17
35 / 100
 274 ms 24244 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],pref[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]
      dp[j][a][0] = max(dp[j][a][0], suff[j - 1][a] - p[j][a]);
 
      //update dp[j][a][1]
      dp[j][a][1] = max(dp[j][a][1], pref[j - 1][a] + 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]);

    pref[j][0] = dp[j][0][1] - p[j][0];
    for (int a =1; a <= n; a++)
      pref[j][a] = max(pref[j][a - 1],dp[j][a][1] - p[j][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 240 ms 20344 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 1 ms 308 KB Output is correct
2 Runtime error 274 ms 24244 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 238 ms 16320 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 4196 KB Output is correct
10 Correct 64 ms 10748 KB Output is correct
11 Correct 8 ms 4224 KB Output is correct
12 Correct 55 ms 10724 KB Output is correct
13 Correct 3 ms 1876 KB Output is correct
14 Correct 59 ms 10724 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 4196 KB Output is correct
10 Correct 64 ms 10748 KB Output is correct
11 Correct 8 ms 4224 KB Output is correct
12 Correct 55 ms 10724 KB Output is correct
13 Correct 3 ms 1876 KB Output is correct
14 Correct 59 ms 10724 KB Output is correct
15 Correct 67 ms 10644 KB Output is correct
16 Correct 3 ms 1876 KB Output is correct
17 Correct 68 ms 12104 KB Output is correct
18 Correct 73 ms 12036 KB Output is correct
19 Correct 76 ms 11980 KB Output is correct
20 Correct 83 ms 12012 KB Output is correct
21 Correct 67 ms 12016 KB Output is correct
22 Correct 110 ms 13164 KB Output is correct
23 Correct 55 ms 10980 KB Output is correct
24 Correct 83 ms 11612 KB Output is correct
25 Correct 73 ms 10684 KB Output is correct
26 Correct 58 ms 10960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 12 ms 4196 KB Output is correct
10 Correct 64 ms 10748 KB Output is correct
11 Correct 8 ms 4224 KB Output is correct
12 Correct 55 ms 10724 KB Output is correct
13 Correct 3 ms 1876 KB Output is correct
14 Correct 59 ms 10724 KB Output is correct
15 Correct 67 ms 10644 KB Output is correct
16 Correct 3 ms 1876 KB Output is correct
17 Correct 68 ms 12104 KB Output is correct
18 Correct 73 ms 12036 KB Output is correct
19 Correct 76 ms 11980 KB Output is correct
20 Correct 83 ms 12012 KB Output is correct
21 Correct 67 ms 12016 KB Output is correct
22 Correct 110 ms 13164 KB Output is correct
23 Correct 55 ms 10980 KB Output is correct
24 Correct 83 ms 11612 KB Output is correct
25 Correct 73 ms 10684 KB Output is correct
26 Correct 58 ms 10960 KB Output is correct
27 Runtime error 4 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 238 ms 16320 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 240 ms 20344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -