Submission #887047

#	Time	Username	Problem	Language	Result	Execution time	Memory
887047		vjudge1	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	326 ms	196604 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], 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][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]);
         }
         mx[i][j]=max({mx[i][j], mx[i-1][j], mx[i][j-1]});
         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: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50