oj.uz

Submission #670494

# Submission time Handle Problem Language Result Execution time Memory
670494 2022-12-09T09:38:16 Z Mahdi Semiexpress (JOI17_semiexpress) C++17
0 / 100
 1 ms 468 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -