Submission #680902

#TimeUsernameProblemLanguageResultExecution timeMemory
680902DennisTranVisiting Singapore (NOI20_visitingsingapore)C++17
10 / 100
196 ms196684 KiB
#pragma GCC optimize("O2") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define int long long using namespace std; const int MAXN = 5005; const long long INF = 0x3f3f3f3f3f3f3f3f; int K, N, M, v[MAXN], s[MAXN], t[MAXN]; long long dp[MAXN], Max[MAXN][MAXN], Ord[MAXN], prv[MAXN]; long long A, B; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //file("TASK"); cin >> K >> N >> M >> A >> B; FOR(i, 1, K) cin >> v[i]; FOR(i, 1, N) cin >> s[i]; FOR(i, 1, M) cin >> t[i]; memset(dp, -INF, sizeof dp); memset(Max, -INF, sizeof Max); memset(Ord, -INF, sizeof Ord); dp[0] = 0; long long ans = -INF; FOR(i, 1, N) { FOR(j, 0, M) prv[j] = dp[j]; FOR(j, 0, M) dp[j] = -INF; long long cur = -INF; FOR(j, 1, M) { if (s[i] == t[j]) { dp[j] = prv[j - 1] + v[t[j]]; if (i >= 2 && j >= 2) dp[j] = max(dp[j], Max[i - 2][j - 2] + v[t[j]] + B * (i + j) + 2 * (A - B)); if (j >= 2) dp[j] = max(dp[j], cur + v[t[j]] + B * j + A - B); if (i >= 2) dp[j] = max(dp[j], Ord[j - 1] + v[t[j]] + B * i + A - B); dp[j] = max(dp[j], v[t[j]] + (j > 1) * A + (j - 1) * B); } Max[i][j] = dp[j] - B *(i + j); Max[i][j] = max(Max[i][j], Max[i - 1][j]); Max[i][j] = max(Max[i][j], Max[i][j - 1]); if (j >= 1) cur = max(cur, prv[j - 1] - (j - 1) * B); //Ord[i][j] = dp[i][j] - i * B; //Ord[i][j] = max(Ord[i][j], Ord[i - 1][j]); if (dp[j] != -INF) ans = max(ans, dp[j] + (M > j) * A + (M - j) * B); } if (i >= 1) { FOR(j, 1, M) { Ord[j] = max(Ord[j], prv[j] - (i - 1) * B); } } } //FOR(i, 1, N) FOR(j, 1, M) cout << dp[i][j] << " \n" [j == M]; cout << ans; cerr << "Time elapsed: " << TIME << " s.\n"; return (0 ^ 0); }

Compilation message (stderr)

VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:28:16: warning: overflow in conversion from 'long long int' to 'int' changes value from '-4557430888798830399' to '-1061109567' [-Woverflow]
   28 |     memset(dp, -INF, sizeof dp);
      |                ^~~~
VisitingSingapore.cpp:29:17: warning: overflow in conversion from 'long long int' to 'int' changes value from '-4557430888798830399' to '-1061109567' [-Woverflow]
   29 |     memset(Max, -INF, sizeof Max);
      |                 ^~~~
VisitingSingapore.cpp:30:17: warning: overflow in conversion from 'long long int' to 'int' changes value from '-4557430888798830399' to '-1061109567' [-Woverflow]
   30 |     memset(Ord, -INF, sizeof Ord);
      |                 ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...