oj.uz

Submission #536053

# Submission time Handle Problem Language Result Execution time Memory
536053 2022-03-12T08:21:17 Z browntoad Collecting Stamps 3 (JOI20_ho_t3) C++14
15 / 100
 87 ms 135288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
 
const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=5005;
const double PI=acos(-1);
 
ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}
 
ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}
 
//=======================================================================================

int dp[205][205][205][2];
signed main (){
    IOS();
    int n, l; cin>>n>>l;
    vector<int> vc(n+2),  ti(n+2);
    REP1(i,n){
        cin>>ti[i];
    }
    REP1(i,n){
        cin>>vc[i];
    }
    ti[n+1]=l;
    //cout<<ti[6]<<endl;
    REP(i,205){
        REP(j,205){
            REP(t, 205){
                REP(k, 2){
                    dp[i][j][t][k]=-inf;
                }
            }
        }
    }
    dp[0][n+1][0][0]=dp[0][n+1][0][1]=0;
    //dp[0][n][l-vc[n]][1]=((l-vc[n])<=ti[n]);
    //dp[1][n+1][vc[1]][0]=((vc[1])<=ti[1]);
    int ans=0;
    REP(i,n+1){
        for (int j=n+1; j>i; j--){
            if (i==0&&j==n+1) continue;
            if (i>0) {
                REP(t, 205){
                    int a=t-(ti[i]-ti[i-1]);
                    if (a>=0) dp[i][j][t][0]=max(dp[i][j][t][0], dp[i-1][j][a][0]);
                    int b=t-(ti[i]+l-ti[j]);
                    if (b>=0) dp[i][j][t][0]=max(dp[i][j][t][0], dp[i-1][j][b][1]);
                    dp[i][j][t][0]+=(vc[i]>=t);
                }
            }
            if (j<=n) {
                REP(t, 205){
                    int a=t-(ti[j+1]-ti[j]);
                    if (a>=0) dp[i][j][t][1]=max(dp[i][j][t][1], dp[i][j+1][a][1]);
                    int b=t-(ti[i]+l-ti[j]);
                    if (b>=0) dp[i][j][t][1]=max(dp[i][j][t][1], dp[i][j+1][b][0]);
                    dp[i][j][t][1]+=(vc[j]>=t);
                }
            }
            REP(t, 205){
                ans=max({ans, dp[i][j][t][0], dp[i][j][t][1]});
            }
        }
    }
    //cout<<dp[0][5][3][1]<<endl;
    //cout<<dp[0][4][7][1]<<endl;
    cout<<ans<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 135124 KB Output is correct
2 Correct 50 ms 135092 KB Output is correct
3 Correct 50 ms 135060 KB Output is correct
4 Correct 52 ms 135092 KB Output is correct
5 Correct 49 ms 135172 KB Output is correct
6 Correct 51 ms 135152 KB Output is correct
7 Correct 50 ms 135080 KB Output is correct
8 Correct 54 ms 135076 KB Output is correct
9 Correct 50 ms 135096 KB Output is correct
10 Correct 51 ms 135132 KB Output is correct
11 Correct 50 ms 135116 KB Output is correct
12 Correct 51 ms 135052 KB Output is correct
13 Correct 51 ms 135160 KB Output is correct
14 Correct 50 ms 135148 KB Output is correct
15 Correct 52 ms 135116 KB Output is correct
16 Correct 51 ms 135124 KB Output is correct
17 Correct 52 ms 135048 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 135124 KB Output is correct
2 Correct 50 ms 135092 KB Output is correct
3 Correct 50 ms 135060 KB Output is correct
4 Correct 52 ms 135092 KB Output is correct
5 Correct 49 ms 135172 KB Output is correct
6 Correct 51 ms 135152 KB Output is correct
7 Correct 50 ms 135080 KB Output is correct
8 Correct 54 ms 135076 KB Output is correct
9 Correct 50 ms 135096 KB Output is correct
10 Correct 51 ms 135132 KB Output is correct
11 Correct 50 ms 135116 KB Output is correct
12 Correct 51 ms 135052 KB Output is correct
13 Correct 51 ms 135160 KB Output is correct
14 Correct 50 ms 135148 KB Output is correct
15 Correct 52 ms 135116 KB Output is correct
16 Correct 51 ms 135124 KB Output is correct
17 Correct 52 ms 135048 KB Output is correct
18 Incorrect 57 ms 135072 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 135124 KB Output is correct
2 Correct 50 ms 135092 KB Output is correct
3 Correct 50 ms 135060 KB Output is correct
4 Correct 52 ms 135092 KB Output is correct
5 Correct 49 ms 135172 KB Output is correct
6 Correct 51 ms 135152 KB Output is correct
7 Correct 50 ms 135080 KB Output is correct
8 Correct 54 ms 135076 KB Output is correct
9 Correct 50 ms 135096 KB Output is correct
10 Correct 51 ms 135132 KB Output is correct
11 Correct 50 ms 135116 KB Output is correct
12 Correct 51 ms 135052 KB Output is correct
13 Correct 51 ms 135160 KB Output is correct
14 Correct 50 ms 135148 KB Output is correct
15 Correct 52 ms 135116 KB Output is correct
16 Correct 51 ms 135124 KB Output is correct
17 Correct 52 ms 135048 KB Output is correct
18 Correct 80 ms 135116 KB Output is correct
19 Correct 71 ms 135092 KB Output is correct
20 Correct 60 ms 135160 KB Output is correct
21 Correct 70 ms 135108 KB Output is correct
22 Correct 74 ms 135240 KB Output is correct
23 Correct 59 ms 135152 KB Output is correct
24 Correct 62 ms 135080 KB Output is correct
25 Correct 60 ms 135080 KB Output is correct
26 Correct 72 ms 135100 KB Output is correct
27 Correct 61 ms 135148 KB Output is correct
28 Correct 59 ms 135176 KB Output is correct
29 Correct 62 ms 135088 KB Output is correct
30 Correct 58 ms 135068 KB Output is correct
31 Correct 60 ms 135132 KB Output is correct
32 Correct 56 ms 135148 KB Output is correct
33 Correct 60 ms 135100 KB Output is correct
34 Correct 55 ms 135120 KB Output is correct
35 Correct 60 ms 135288 KB Output is correct
36 Correct 55 ms 135132 KB Output is correct
37 Correct 59 ms 135128 KB Output is correct
38 Correct 55 ms 135116 KB Output is correct
39 Correct 59 ms 135072 KB Output is correct
40 Correct 56 ms 135132 KB Output is correct
41 Correct 87 ms 135152 KB Output is correct
42 Correct 75 ms 135116 KB Output is correct
43 Correct 85 ms 135184 KB Output is correct
44 Correct 77 ms 135128 KB Output is correct
45 Correct 84 ms 135176 KB Output is correct
46 Correct 75 ms 135180 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 135124 KB Output is correct
2 Correct 50 ms 135092 KB Output is correct
3 Correct 50 ms 135060 KB Output is correct
4 Correct 52 ms 135092 KB Output is correct
5 Correct 49 ms 135172 KB Output is correct
6 Correct 51 ms 135152 KB Output is correct
7 Correct 50 ms 135080 KB Output is correct
8 Correct 54 ms 135076 KB Output is correct
9 Correct 50 ms 135096 KB Output is correct
10 Correct 51 ms 135132 KB Output is correct
11 Correct 50 ms 135116 KB Output is correct
12 Correct 51 ms 135052 KB Output is correct
13 Correct 51 ms 135160 KB Output is correct
14 Correct 50 ms 135148 KB Output is correct
15 Correct 52 ms 135116 KB Output is correct
16 Correct 51 ms 135124 KB Output is correct
17 Correct 52 ms 135048 KB Output is correct
18 Incorrect 57 ms 135072 KB Output isn't correct
19 Halted 0 ms 0 KB -