oj.uz

Submission #634126

# Submission time Handle Problem Language Result Execution time Memory
634126 2022-08-23T20:38:33 Z urosk Collecting Stamps 3 (JOI20_ho_t3) C++14
100 / 100
 117 ms 130892 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
void ckmin(ll &x,ll y){x = min(x,y);}
#define maxn 205
ll n,L;
ll a[maxn],t[maxn];
ll b[maxn];
ll dp[maxn][maxn][2][maxn];
int main(){
	daj_mi_malo_vremena
    cin >> n >> L;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    for(ll i = 1;i<=n;i++) b[i] = L-a[i];
    reverse(b+1,b+n+1);
    for(ll i = 1;i<=n;i++) cin >> t[i];
    for(ll i = 0;i<=n;i++) for(ll j = 0;j<=n;j++) for(ll e = 0;e<=1;e++) for(ll p = 0;p<=n;p++)
    dp[i][j][e][p] = llinf;
    dp[1][0][1][a[1]<=t[1]] = a[1];
    dp[1][0][1][0] = a[1];
    dp[0][1][0][b[1]<=t[n]] = b[1];
    dp[0][1][0][0] = b[1];
    for(ll s = 1;s<n;s++){
        for(ll l = 0;l<=s;l++){
            ll r = s-l;
            for(ll e = 0;e<=1;e++){
                for(ll p = 0;p<=n;p++){
                    ll time = dp[l][r][e][p];
                    ll dl = a[l+1]-a[l];
                    if(!e) dl = b[r] + a[l+1];
                    ll dr = b[r+1] + a[l];
                    if(!e) dr = b[r+1] - b[r];
                    if(s==n-1) dl = min(a[l+1]-a[l],b[r]+a[l+1]);
                    if(s==n-1) dr = min(b[r+1]-b[r],b[r+1]+a[l]);
                    ckmin(dp[l+1][r][1][p+((time+dl)<=t[l+1])],time+dl);
                    ckmin(dp[l][r+1][0][p+((time+dr)<=t[n-(r+1)+1])],time+dr);
                }
            }
        }
    }
    ll ans = 0;
    for(ll s = 1;s<=n;s++){
        for(ll l = 0;l<=s;l++){
            ll r = s-l;
            for(ll e = 0;e<=1;e++){
                for(ll p = 0;p<=n;p++){
                    if(dp[l][r][e][p]<llinf) ans = max(ans,p);
                }
            }
        }
    }
    cout<<ans<<endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 1092 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 1108 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 1 ms 1096 KB Output is correct
26 Correct 1 ms 980 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 1112 KB Output is correct
30 Correct 1 ms 1108 KB Output is correct
31 Correct 1 ms 980 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1108 KB Output is correct
34 Correct 1 ms 1108 KB Output is correct
35 Correct 1 ms 1108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 91 ms 104964 KB Output is correct
19 Correct 52 ms 63660 KB Output is correct
20 Correct 24 ms 34064 KB Output is correct
21 Correct 47 ms 60108 KB Output is correct
22 Correct 63 ms 78008 KB Output is correct
23 Correct 20 ms 28912 KB Output is correct
24 Correct 15 ms 22740 KB Output is correct
25 Correct 23 ms 28336 KB Output is correct
26 Correct 7 ms 11092 KB Output is correct
27 Correct 23 ms 29652 KB Output is correct
28 Correct 14 ms 21064 KB Output is correct
29 Correct 22 ms 30164 KB Output is correct
30 Correct 16 ms 23804 KB Output is correct
31 Correct 19 ms 28416 KB Output is correct
32 Correct 9 ms 14924 KB Output is correct
33 Correct 19 ms 28396 KB Output is correct
34 Correct 5 ms 10184 KB Output is correct
35 Correct 19 ms 27732 KB Output is correct
36 Correct 8 ms 13256 KB Output is correct
37 Correct 21 ms 29524 KB Output is correct
38 Correct 12 ms 16300 KB Output is correct
39 Correct 22 ms 30888 KB Output is correct
40 Correct 12 ms 18132 KB Output is correct
41 Correct 114 ms 129448 KB Output is correct
42 Correct 71 ms 87264 KB Output is correct
43 Correct 112 ms 129384 KB Output is correct
44 Correct 73 ms 86228 KB Output is correct
45 Correct 113 ms 129392 KB Output is correct
46 Correct 72 ms 87244 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 1092 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 1108 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 1 ms 1096 KB Output is correct
26 Correct 1 ms 980 KB Output is correct
27 Correct 1 ms 588 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 1112 KB Output is correct
30 Correct 1 ms 1108 KB Output is correct
31 Correct 1 ms 980 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1108 KB Output is correct
34 Correct 1 ms 1108 KB Output is correct
35 Correct 1 ms 1108 KB Output is correct
36 Correct 91 ms 104964 KB Output is correct
37 Correct 52 ms 63660 KB Output is correct
38 Correct 24 ms 34064 KB Output is correct
39 Correct 47 ms 60108 KB Output is correct
40 Correct 63 ms 78008 KB Output is correct
41 Correct 20 ms 28912 KB Output is correct
42 Correct 15 ms 22740 KB Output is correct
43 Correct 23 ms 28336 KB Output is correct
44 Correct 7 ms 11092 KB Output is correct
45 Correct 23 ms 29652 KB Output is correct
46 Correct 14 ms 21064 KB Output is correct
47 Correct 22 ms 30164 KB Output is correct
48 Correct 16 ms 23804 KB Output is correct
49 Correct 19 ms 28416 KB Output is correct
50 Correct 9 ms 14924 KB Output is correct
51 Correct 19 ms 28396 KB Output is correct
52 Correct 5 ms 10184 KB Output is correct
53 Correct 19 ms 27732 KB Output is correct
54 Correct 8 ms 13256 KB Output is correct
55 Correct 21 ms 29524 KB Output is correct
56 Correct 12 ms 16300 KB Output is correct
57 Correct 22 ms 30888 KB Output is correct
58 Correct 12 ms 18132 KB Output is correct
59 Correct 114 ms 129448 KB Output is correct
60 Correct 71 ms 87264 KB Output is correct
61 Correct 112 ms 129384 KB Output is correct
62 Correct 73 ms 86228 KB Output is correct
63 Correct 113 ms 129392 KB Output is correct
64 Correct 72 ms 87244 KB Output is correct
65 Correct 100 ms 116812 KB Output is correct
66 Correct 93 ms 107276 KB Output is correct
67 Correct 86 ms 102604 KB Output is correct
68 Correct 77 ms 94716 KB Output is correct
69 Correct 100 ms 115704 KB Output is correct
70 Correct 95 ms 110880 KB Output is correct
71 Correct 95 ms 111980 KB Output is correct
72 Correct 98 ms 113232 KB Output is correct
73 Correct 88 ms 105000 KB Output is correct
74 Correct 85 ms 98164 KB Output is correct
75 Correct 91 ms 108436 KB Output is correct
76 Correct 112 ms 124384 KB Output is correct
77 Correct 107 ms 124352 KB Output is correct
78 Correct 80 ms 95912 KB Output is correct
79 Correct 88 ms 99284 KB Output is correct
80 Correct 104 ms 121872 KB Output is correct
81 Correct 88 ms 100428 KB Output is correct
82 Correct 92 ms 106160 KB Output is correct
83 Correct 113 ms 129356 KB Output is correct
84 Correct 95 ms 110764 KB Output is correct
85 Correct 105 ms 120524 KB Output is correct
86 Correct 101 ms 118080 KB Output is correct
87 Correct 92 ms 108508 KB Output is correct
88 Correct 117 ms 130764 KB Output is correct
89 Correct 116 ms 130764 KB Output is correct
90 Correct 97 ms 109688 KB Output is correct
91 Correct 115 ms 130892 KB Output is correct
92 Correct 116 ms 130764 KB Output is correct
93 Correct 113 ms 128108 KB Output is correct