Submission #1143051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143051		ByeWorld	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	463 ms	17204 KiB

semiexpress

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3010;
const int SQRT = 550;
const int MAXA = 50;
const int LOG = 60;
const int INF = 1e9+10;
const ld EPS = 1e-12;
const int MOD = 1e9+7;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, m, k, a, b, c, t;
int s[MAXN], dp[MAXN][MAXN], add[MAXN];

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k; k -= m;
    cin>>a>>b>>c>>t;
    for(int i=1; i<=m; i++)
        cin >> s[i], s[i]--;

    for(int i=1; i<=m; i++)
        for(int j=0; j<=k; j++) dp[i][j] = -INF;
    dp[1][0] = 0;

    for(int i=2; i<=m; i++){
        int sisa = t-s[i-1]*b; // ke s[i-1]
        int dis = s[i]-s[i-1]-1;
        add[0] = max(0ll, sisa)/a; 

        for(int j=1; j<=k; j++){
            int te = sisa-add[j-1]*c;
            if(te>=c) 
                add[j] = add[j-1]+(te-c)/a+1;
            else add[j] = add[j-1];
        }
        for(int j=0; j<=k; j++) add[j] = min(add[j], dis);

        // cout << i << " i\n";
        // for(int j=0; j<=k; j++) cout << add[j] << " \n"[j==k];
        for(int j=0; j<=k; j++){
            for(int kur=0; kur<=j; kur++)
                chmx(dp[i][j], dp[i-1][j-kur]+add[kur]);

            if(s[i]*b <= t) dp[i][j]++;
            // cout << i << ' ' << j << ' ' <<dp[i][j] << " ij\n";
        }
    }
    cout << dp[m][k] << '\n';
}

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