Submission #1307642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307642		ballbreaker	Semiexpress (JOI17_semiexpress)	C++20	0 / 100	1 ms	568 KiB

semiexpress

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2")
#define int long long
using namespace std;
main() {
    int n, m, k;
    cin >> n >> m >> k;
    int A, B, C;
    cin >> A >> B >> C;
    int t;
    cin >> t;
    int s[m + 1];
    for (int i = 1; i <= m; i++) {
        cin >> s[i];
    }
    k -= m;
    int dp[m + 1][k + 1] = {};
    int f[m + 1][k + 1] = {};
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = -LLONG_MAX / 2;
            f[i][j] = -LLONG_MAX / 2;
        }
        f[i][0] = 0;
    }
    dp[0][0] = 0;
    for (int i = 2; i <= m; i++) {
        if (s[i] * B <= t) {
            dp[0][0]++;
        }
    }
    // cout << t << endl;
    for (int i = 1; i < m; i++) {
        // cout << s[i] + 1 << ' ' << s[i + 1] << endl;
        int st = (s[i] - 1) * B;
        if (st > t) {
            continue;
        }
        int o = 0;
        // cout << "? time: ";
        bool ch = 1;
        for (int j = s[i] + 1; j < s[i + 1]; j++) {
            st += A;
            if (st > t) {
                // cout << j << endl;
                st = (s[i] - 1) * B + C * (j - s[i]);
                f[i][o] = (j - s[i] - 1);
                if (st > t) {
                    ch = 0;
                    break;
                }
                o++;
            }
            // cout << st << ' ';
        }
        if (ch) {
            f[i][o] = s[i + 1] - s[i] - 1;
        }
        // cout << "timer: ";
        for (int y = 0; y <= k; y++) {
            if (f[i][y] != -LLONG_MAX / 2) {
                for (int j = 0; j + y <= k; j++) {
                    dp[i][j + y] = max(dp[i - 1][j] + f[i][y], dp[i][j + y]);
                }
                // cout << f[i][y] << ' ';
            }
        }
        // cout << endl;
    }
    int mx = 0;
    for (int j = 0; j <= k; j++) {
        mx = max(mx, dp[m - 1][j]);
    }
    cout << mx;
}

Compilation message (stderr)

semiexpress.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main() {
      | ^~~~

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