oj.uz

Submission #887046

# Submission time Handle Problem Language Result Execution time Memory
887046 2023-12-13T14:30:42 Z vjudge1 Visiting Singapore (NOI20_visitingsingapore) C++14
10 / 100
 53 ms 196700 KB 
#include<bits/stdc++.h>

using namespace std;

// struct FenwickTree2d{
//    int n, m;
//    vector<vector<int>> t;
//    void init(int _n, int _m){
//       n=_n+1; m=_m+1;
//       vector<vector<int>>(n+1, vector<int>(m+1, -1e9)).swap(t);
//    }
//    void update(int x, int y, int val){
//       ++x; ++y;
//       for (int i=x; i<=n; i+=i&(-i)) for (int j=y; j<=m; j+=j&(-j)) t[i][j]=max(t[i][j], val);
//    }
//    int get(int x, int y){
//       ++x; ++y;
//       int ans=-1e9;
//       for (int i=x; i; i-=i&(-i)) for (int j=y; j; j-=j&(-j)) ans=max(ans, t[i][j]);
//       return ans;
//    }
// } bit2d;

const int N=5001;
int n, m, A, B, k, v[N], s[N], t[N], f[2][N], r[2][N], c[N][N], mx[N][N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   for (int i=0; i<2; ++i) for (int j=0; j<N; ++j) f[i][j]=-1e9, r[i][j]=-1e9;
   for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) c[i][j]=mx[i][j]=-1e9;
   cin >> k >> n >> m >> A >> B;
   for (int i=1; i<=k; ++i) cin >> v[i];
   for (int i=1; i<=n; ++i) cin >> s[i];
   for (int i=1; i<=m; ++i) cin >> t[i];
   // bit2d.init(m, n);
   for (int j=0; j<=n; ++j){
      f[0][j]=0;
      r[0][j]=f[0][j]-B*j;
      c[0][j]=f[0][j];
      mx[0][j]=-B*j;
      // bit2d.update(0, j, -B*j);
   }
   for (int i=0; i<2; ++i) for (int j=1; j<=n; ++j){
      r[i][j]=max(r[i][j], r[i][j-1]);
   }
   for (int i=1; i<=m; ++i) for (int j=0; j<=n; ++j){
      c[i][j]=max(c[i][j], c[i-1][j]);
   }
   for (int i=1; i<=n; ++i) mx[0][i]=max(mx[0][i], mx[0][i-1]);
   for (int i=1; i<=m; ++i) mx[i][0]=max(mx[i][0], mx[i-1][0]);
   int ans=A+B*m;
   for (int i=1; i<=m; ++i){
      for (int j=1; j<=n; ++j){
         if (s[j]==t[i]){
            if (i>=2 && j>=2) f[1][j]=max(f[1][j], mx[i-2][j-2]+A+A+B*(i-1)+B*(j-1)+v[t[i]]);
            if (i>=2) f[1][j]=max(f[1][j], c[i-2][j-1]+A+B*(i-1)+v[t[i]]);
            if (j>=2) f[1][j]=max(f[1][j], r[0][j-2]+A+B*(j-1)+v[t[i]]);
            f[1][j]=max(f[1][j], f[0][j-1]+v[t[i]]);
            mx[i][j]=max({mx[i-1][j], mx[i][j-1], f[1][j]-B*i-B*j});
            if (i!=m) ans=max(ans, f[1][j]+A+B*(m-i));
            else ans=max(ans, f[1][j]);
         }
         r[1][j]=max({r[1][j], r[1][j-1], f[1][j]-B*j});
         c[i][j]=max({c[i][j], c[i-1][j], f[1][j]-B*i});
      }
      memcpy(f[0], f[1], sizeof f[1]);
      memcpy(r[0], r[1], sizeof r[1]);
      for (int j=0; j<=n; ++j) f[1][j]=-1e9, r[1][j]=-1e9;
   }
   cout << ans;
   return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 196208 KB Output is correct
2 Correct 46 ms 196176 KB Output is correct
3 Correct 39 ms 196284 KB Output is correct
4 Correct 36 ms 196180 KB Output is correct
5 Correct 36 ms 196136 KB Output is correct
6 Correct 38 ms 196184 KB Output is correct
7 Correct 36 ms 196180 KB Output is correct
8 Correct 36 ms 196112 KB Output is correct
9 Correct 44 ms 196700 KB Output is correct
10 Correct 47 ms 196176 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 196220 KB Output is correct
2 Correct 35 ms 196188 KB Output is correct
3 Correct 39 ms 196180 KB Output is correct
4 Correct 36 ms 196176 KB Output is correct
5 Correct 37 ms 196176 KB Output is correct
6 Correct 40 ms 196188 KB Output is correct
7 Correct 42 ms 196176 KB Output is correct
8 Correct 43 ms 196264 KB Output is correct
9 Correct 36 ms 196184 KB Output is correct
10 Correct 48 ms 196176 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 196328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 196328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 196328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 196284 KB Output is correct
2 Correct 35 ms 196180 KB Output is correct
3 Correct 35 ms 196104 KB Output is correct
4 Incorrect 35 ms 196296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 196208 KB Output is correct
2 Correct 46 ms 196176 KB Output is correct
3 Correct 39 ms 196284 KB Output is correct
4 Correct 36 ms 196180 KB Output is correct
5 Correct 36 ms 196136 KB Output is correct
6 Correct 38 ms 196184 KB Output is correct
7 Correct 36 ms 196180 KB Output is correct
8 Correct 36 ms 196112 KB Output is correct
9 Correct 44 ms 196700 KB Output is correct
10 Correct 47 ms 196176 KB Output is correct
11 Correct 36 ms 196220 KB Output is correct
12 Correct 35 ms 196188 KB Output is correct
13 Correct 39 ms 196180 KB Output is correct
14 Correct 36 ms 196176 KB Output is correct
15 Correct 37 ms 196176 KB Output is correct
16 Correct 40 ms 196188 KB Output is correct
17 Correct 42 ms 196176 KB Output is correct
18 Correct 43 ms 196264 KB Output is correct
19 Correct 36 ms 196184 KB Output is correct
20 Correct 48 ms 196176 KB Output is correct
21 Incorrect 50 ms 196328 KB Output isn't correct
22 Halted 0 ms 0 KB -