Submission #670494

#	Time	Username	Problem	Language	Result	Execution time	Memory
670494		Mahdi	Semiexpress (JOI17_semiexpress)	C++17	0 / 100	1 ms	468 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=305;
int n, m, k, pd[N][N], dp[N][N];
int a, b, c;
ll T, s[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>k>>a>>b>>c>>T;
    for(int i=1;i<=m;++i)
        cin>>s[i];
    s[m+1]=n+1;
    for(int i=1;i<=m;++i){
        ll h=b*s[i]-b;
        if(h>T)
            break;
        h=T-h;
        ll x=min(s[i]+h/a, s[i+1]-1);
        pd[i][0]=x-s[i]+1;
        for(int j=1;j<=k-m;++j){
            h=b*s[i]-b+c*(x-s[i]+1);
            if(h>T)
                break;
            h=T-h;
            x=min(x+1+h/a, s[i+1]-1);
            pd[i][j]=x-s[i]+1;
        }
        for(int j=1;j<=k-m;++j)
            pd[i][j]=max(pd[i][j-1], pd[i][j]);
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=k-m;++j){
            for(int jj=0;jj<=j;++jj)
                dp[i][j]=max(dp[i][j], dp[i-1][j-jj]+pd[i][jj]);
        }
    }
    cout<<dp[m][k-m]-1<<'\n';
}

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