Submission #299317

#	Time	Username	Problem	Language	Result	Execution time	Memory
299317		BeanZ	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	2 ms	1152 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
ll dp[305][305];
ll s[305], len[305], p[305], last[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;
        ll T;
        cin >> T;
        for (int i = 1; i <= m; i++) cin >> s[i];
        len[1] = 0;
        ll cur = 1;
        for (int i = 1; i <= n; i++){
                last[i] = cur;
                if ((cur + 1) <= m && s[cur + 1] <= i) cur++;
                len[i] = (s[cur] - 1) * B + (i - s[cur]) * C;
                ll dist = len[i];
                if (dist <= T) p[i] = 1;
                else p[i] = 0;
                for (int j = i + 1; j <= n; j++){
                        dist = dist + A;
                        if (dist > T) break;
                        p[i]++;
                }
                //cout << last[i] << " " << p[i] << endl;
        }
        //cout << endl << endl;
        ll ans = 0;
        for (int i = 1; i <= n; i++){
                for (int j = 0; j <= k; j++) dp[i][j] = -1e9;
        }
        dp[1][1] = p[1];
        for (int i = 2; i <= n; i++){
                for (int j = 1; j <= k; j++){
                        for (int t = s[last[i]]; t < i; t++){
                                dp[i][j] = max(dp[i][j], dp[t][j - 1] - p[t] + min((ll)(i - t), p[t]) + p[i]);
                                ans = max(ans, dp[i][j]);
                                //cout << i << " " << j << " " << dp[i][j] << endl;
                        }
                }
        }
        cout << ans - 1;
}
/*
eraae
*/

Compilation message (stderr)

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

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 52