oj.uz

Submission #644104

# Submission time Handle Problem Language Result Execution time Memory
644104 2022-09-23T20:15:47 Z NintsiChkhaidze Catfish Farm (IOI22_fish) C++17
52 / 100
 777 ms 154844 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
 
const int N = 3005;
ll p[N][N],dp[N][5],suff[N],pref[N],prc[N][N];
vector <int> v[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];
    v[X[i] + 1].pb(Y[i]);
    v[X[i] - 1].pb(Y[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++){
    v[j].pb(0); 
    v[j].pb(n);

    for (int i = 1; i <= n; i++)
        dp[i][0] = dp[i][1] = 0;
    
    for (int a: v[j]){
      dp[a][0] = suff[a] - p[j][a];
      dp[a][1] = pref[a] + p[j - 1][a];
      if (j >= 3) dp[a][1] = max(dp[a][1], prc[j - 2][a] + p[j - 1][a]);
    }
    
    for (int a = n; a >= 0; a--)
      suff[a] = max(suff[a+1],max(dp[a][0],dp[a][1]) + p[j + 1][a]);
 
    pref[0] = dp[0][1] - p[j][0];
    for (int a =1; a <= n; a++)
      pref[a] = max(pref[a - 1],dp[a][1] - p[j][a]);
 
    prc[j][0] = max(dp[0][0],dp[0][1]);
    for (int a = 1; a <= n; a++)
        prc[j][a] = max(prc[j][a - 1], max(dp[a][0],dp[a][1])); 
  }
 
  ll ans = 0;
  for (int a = 0; a <= n; a++)
      ans=max({ans,dp[a][0],dp[a][1]});
  return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 720 ms 149448 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 340 KB Output is correct
2 Runtime error 757 ms 154468 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 777 ms 143816 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 6 ms 4308 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 3 ms 4180 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 3 ms 4180 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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 6 ms 4308 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 3 ms 4180 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 19 ms 6412 KB Output is correct
18 Correct 17 ms 6604 KB Output is correct
19 Correct 16 ms 6544 KB Output is correct
20 Correct 17 ms 6552 KB Output is correct
21 Correct 17 ms 6524 KB Output is correct
22 Correct 34 ms 9072 KB Output is correct
23 Correct 6 ms 4564 KB Output is correct
24 Correct 12 ms 5604 KB Output is correct
25 Correct 3 ms 4180 KB Output is correct
26 Correct 6 ms 4584 KB Output is correct

Subtask #6
17.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 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1876 KB Output is correct
10 Correct 6 ms 4308 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 3 ms 4180 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 19 ms 6412 KB Output is correct
18 Correct 17 ms 6604 KB Output is correct
19 Correct 16 ms 6544 KB Output is correct
20 Correct 17 ms 6552 KB Output is correct
21 Correct 17 ms 6524 KB Output is correct
22 Correct 34 ms 9072 KB Output is correct
23 Correct 6 ms 4564 KB Output is correct
24 Correct 12 ms 5604 KB Output is correct
25 Correct 3 ms 4180 KB Output is correct
26 Correct 6 ms 4584 KB Output is correct
27 Correct 141 ms 141720 KB Output is correct
28 Correct 85 ms 24880 KB Output is correct
29 Correct 257 ms 154844 KB Output is correct
30 Correct 265 ms 154680 KB Output is correct
31 Correct 279 ms 154656 KB Output is correct
32 Correct 101 ms 24064 KB Output is correct
33 Correct 264 ms 154640 KB Output is correct
34 Correct 271 ms 153832 KB Output is correct
35 Correct 188 ms 147584 KB Output is correct
36 Correct 256 ms 154484 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 777 ms 143816 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 720 ms 149448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -