Submission #887043

#	Time	Username	Problem	Language	Result	Execution time	Memory
887043		vjudge1	Visiting Singapore (NOI20_visitingsingapore)	C++14	23 / 100	2058 ms	196480 KiB

VisitingSingapore

#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];

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]=-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];
      bit2d.update(0, j, 0);
   }
   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]);
   }
   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], bit2d.get(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]]);
            bit2d.update(i, j, 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 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50