oj.uz

Submission #299053

# Submission time Handle Problem Language Result Execution time Memory
299053 2020-09-14T12:48:32 Z BeanZ Semiexpress (JOI17_semiexpress) C++14
18 / 100
 3 ms 1792 KB 
#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 = 1;
        for (int i = 2; i <= n; i++){
                if (st[i]) cnt++;
                for (int j = 1; 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]);
                        if (j < cnt) continue;
                        dist = len[i];
                        if (dist <= T && (st[i] || (st[i] == 0 && j > cnt))) dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + 1);
                        if ((st[i] == 0 && j > cnt) || st[i]){
                                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

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |                 freopen("test.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 2 ms 1664 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 2 ms 1664 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct
9 Correct 2 ms 1792 KB Output is correct
10 Correct 2 ms 1792 KB Output is correct
11 Correct 2 ms 1792 KB Output is correct
12 Correct 2 ms 1792 KB Output is correct
13 Correct 3 ms 1792 KB Output is correct
14 Incorrect 1 ms 1536 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 2 ms 1664 KB Output is correct
4 Correct 1 ms 1536 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 2 ms 1536 KB Output is correct
7 Correct 2 ms 1664 KB Output is correct
8 Correct 1 ms 1664 KB Output is correct
9 Correct 2 ms 1792 KB Output is correct
10 Correct 2 ms 1792 KB Output is correct
11 Correct 2 ms 1792 KB Output is correct
12 Correct 2 ms 1792 KB Output is correct
13 Correct 3 ms 1792 KB Output is correct
14 Incorrect 1 ms 1536 KB Output isn't correct
15 Halted 0 ms 0 KB -