oj.uz

Submission #563667

# Submission time Handle Problem Language Result Execution time Memory
563667 2022-05-17T21:43:12 Z groshi Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 468 KB 
#include<iostream>
#include<vector>
using namespace std;
vector<int> Q;
int dp[210][210][210][2];
int t[300],x[400];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l;
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        cin>>x[i];
    for(int i=1;i<=n;i++)
        cin>>t[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
            {
                dp[i][j][k][0]=1000000000;
                dp[i][j][k][1]=1000000000;
            }
    x[n+1]=l;
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    for(int k=0;k<=n;k++)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j+i<n;j++)
            {
                int ile=x[i]+(l-x[n+1-j]);
                dp[i][j][k][0]=min(dp[i][j][k][1]+ile,dp[i][j][k][0]);
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j][k][0]+ile);
                int do_lewej=dp[i][j][k][0]+(x[i+1]-x[i]);
                //cout<<do_lewej<<"\n";
                if(do_lewej<=t[i+1])
                    dp[i+1][j][k+1][0]=min(dp[i+1][j][k+1][0],do_lewej);
                else dp[i+1][j][k][0]=min(dp[i+1][j][k][0],do_lewej);
                int do_prawej=dp[i][j][k][1]+(x[n+1-j]-x[n+1-j-1]);
                //cout<<do_prawej<<"\n";
                if(do_prawej<=t[n+1-j-1])
                    dp[i][j+1][k+1][1]=min(dp[i][j+1][k+1][1],do_prawej);
                else dp[i][j+1][k][1]=min(dp[i][j+1][k][1],do_prawej);
            }
        }
    }
    int wynik=0;
    for(int i=0;i<=n;i++)
        for(int j=1;j+i<=n;j++)
             for(int k=0;k<=n;k++)
                 if(dp[i][j][k][0]!=1e9 || dp[i][j][k][1]!=1e9)
                    wynik=max(wynik,k);
    cout<<wynik;
    return 0;
}

Subtask #1
0 / 5.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 / 10.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 / 10.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 #4
0 / 75.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 -