# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
299041 | BeanZ | Semiexpress (JOI17_semiexpress) | C++14 | 1 ms | 1664 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll dp[305][305][2];
ll s[305], len[305];
bool st[305];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, m, k;
cin >> n >> m >> k;
ll A, B, C;
cin >> A >> B >> C;
dp[1][1][1] = 1;
ll T;
cin >> T;
for (int i = 1; i <= m; i++) cin >> s[i], st[s[i]] = 1;
len[1] = 0;
ll cur = 1;
for (int i = 2; i <= n; i++){
if ((cur + 1) <= m && s[cur + 1] <= i) cur++;
len[i] = (s[cur] - 1) * B + (i - s[cur]) * C;
//cout << len[i] << " ";
}
//cout << endl;
ll cnt = 1;
ll dist = 0;
for (int t = 2; t <= n; t++){
dist = dist + A;
if (dist > T) break;
dp[t][1][0] = max(dp[t][1][0], dp[1][1][1] + t - 1);
}
ll ans = 0;
for (int i = 2; i <= n; i++){
if (st[i]) cnt++;
for (int j = cnt + (st[i] == 0); j <= (cnt + (k - m)); j++){
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][0]);
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1]);
dist = len[i];
if (dist <= T) dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + 1);
for (int t = i + 1; t <= n; t++){
dist = dist + A;
if (dist > T) break;
dp[t][j][0] = max(dp[t][j][0], dp[i][j][1] + t - i);
}
ans = max(ans, dp[i][j][0]);
ans = max(ans, dp[i][j][1]);
//cout << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << endl;
}
}
//cout << len[10] << endl;
//cout << len[8] << " ";
//cout << dp[2][2][1] << endl;
cout << ans - 1;
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |