oj.uz

Submission #241342

# Submission time Handle Problem Language Result Execution time Memory
241342 2020-06-24T04:40:59 Z kal013 Collecting Stamps 3 (JOI20_ho_t3) C++17
100 / 100
 390 ms 526968 KB 
/*/ Author: kal013 /*/
// #pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;

template<class T> 
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update> ;

template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<class T> ostream& operator<<(ostream &os, vector<T> V) {
    os << "[ ";
    for(auto v : V) os << v << " ";
    return os << "]";
}
template<class T> ostream& operator<<(ostream &os, set<T> S){
    os << "{ ";
    for(auto s:S) os<<s<<" ";
    return os<<"}";
}
template<class T> ostream& operator<<(ostream &os, unordered_set<T> S){
    os << "{ ";
    for(auto s:S) os<<s<<" ";
    return os<<"}";
}
template<class T> ostream& operator<<(ostream &os, ordered_set<T> S){
    os << "{ ";
    for(auto s:S) os<<s<<" ";
    return os<<"}";
}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
    os << "{ ";
    for(auto m:M) os<<"("<<m.first<<":"<<m.second<<") ";
    return os<<"}";
}
template<class L, class R> ostream& operator<<(ostream &os, unordered_map<L,R> M) {
    os << "{ ";
    for(auto m:M) os<<"("<<m.first<<":"<<m.second<<") ";
    return os<<"}";
}
template<class L, class R, class chash = std::hash<R> > ostream& operator<<(ostream &os, gp_hash_table<L,R,chash> M) {
    os << "{ ";
    for(auto m:M) os<<"("<<m.first<<":"<<m.second<<") ";
    return os<<"}";
}

#define TRACE
#ifdef TRACE
    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');
        cerr.write(names, comma - names) << " : " << arg1<<" | ";
        __f(comma+1, args...);
    }
#else
    #define trace(...) 1
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int64_t random_long(long long l,long long r){
    uniform_int_distribution<int64_t> generator(l,r);
    return generator(rng);
}
inline int64_t random_long(){
    uniform_int_distribution<int64_t> generator(LLONG_MIN,LLONG_MAX);
    return generator(rng);
}


/*/---------------------------Defines----------------------/*/
typedef vector<int> vi;
typedef pair<int,int> pii;

#define ll long long
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(v) (v).begin(),(v).end()
/*/-----------------------Modular Arithmetic---------------/*/

const int mod=1e9+7;
inline int add(int x,int y){
    x+=y;
    if (x>=mod) return x-mod;
    return x;
}
inline int sub(int x,int y){
    x-=y;
    if (x<0) return x+mod;
    return x;
}
inline int mul(int x,int y){
    return (x*1ll*y)%mod;
}
inline int power(int x,int y){
    int ans=1;
    while(y){
        if (y&1) ans=mul(ans,x);
        x=mul(x,x);
        y>>=1;
    }
    return ans;
}
inline int inv(int x){
    return power(x,mod-2);
}
/*/-----------------------------Code begins----------------------------------/*/
const int N = 405;
const int M = 205;

long long dp[N][N][2][M];
const ll INF = 1e15+10;
void solve(){
    int n;
    ll l;
    cin>>n>>l;
    vector<ll> X(2*n + 1),T(2*n + 1);
    for(int i = 0; i < n; ++i){
    	cin>>X[i];
    }
    X[n] = l;
    for(int i = 0; i<n; ++i){
    	X[n+i+1] = l + X[i];
    }


    for(int i = 0; i < n; ++i){
    	cin>>T[i];
    }
    T[n] = -1;

    for(int i = 0; i<n; ++i){
    	T[n+i+1] = T[i];
    }
    int ans = 0;

    for(int i = 0 ; i < N; ++i){
    	for(int j = 0; j < N ; ++j){
    		for(int k = 0 ; k < 2; ++k){
    			for(int l = 0; l < M; ++l){
    				dp[i][j][k][l] = INF;
    			}
    		}
    	}
    }

    dp[n][n][0][0] = 0;
    dp[n][n][1][0] = 0;
    for(int len = 1; len <= n; ++len){

    	for(int l_id = n; l_id + len >= n; --l_id){
    		int r_id = l_id + len;

    		for(int pos = 0;  pos < 2; ++pos){
    			for(int k = 0; k <= len ; ++k){
    				long long&  cur_dp = dp[l_id][r_id][pos][k];
    				cur_dp = INF;

    				if (pos == 0){
    					ll x_dif = X[l_id+1] - X[l_id];
    					cur_dp = min(dp[l_id + 1][r_id][pos][k] + x_dif, cur_dp);
    					cur_dp = min(dp[l_id+1][r_id][pos^1][k] + X[r_id] - X[l_id],cur_dp);
    					if (k >= 1 && dp[l_id+1][r_id][pos][k-1] + x_dif <= T[l_id]){
    						cur_dp = min(cur_dp,dp[l_id+1][r_id][pos][k-1] + x_dif);
    					}
    					if (k >= 1 && dp[l_id+1][r_id][pos^1][k-1] + X[r_id] - X[l_id] <= T[l_id]){
    						cur_dp = min(cur_dp, dp[l_id+1][r_id][pos^1][k-1] + X[r_id] - X[l_id]);
    					}
    				}
    				else{
    					ll x_dif = X[r_id] - X[r_id-1];
    					cur_dp = min(dp[l_id][r_id-1][pos][k] + x_dif, cur_dp);
    					cur_dp = min(dp[l_id][r_id-1][pos^1][k] + X[r_id] - X[l_id], cur_dp);

    					if (k >= 1 && dp[l_id][r_id-1][pos][k-1] + x_dif <= T[r_id]){
    						cur_dp = min(cur_dp,dp[l_id][r_id-1][pos][k-1] + x_dif);
    					}
    					if (k >= 1 && dp[l_id][r_id-1][pos^1][k-1] + X[r_id] - X[l_id] <= T[r_id]){
    						cur_dp = min(cur_dp, dp[l_id][r_id-1][pos^1][k-1] + X[r_id] - X[l_id]);
    					}	
    				}

    				if (dp[l_id][r_id][pos][k] < INF){
    					ans = max(ans,k);
    				} 

    			}
    		}
    	}
    }

    cout<<ans<<endl;
}
int main(){
    // Use "set_name".max_load_factor(0.25);"set_name".reserve(512); with unordered set
    // Or use gp_hash_table<X,null_type>
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cout<<fixed<<setprecision(25);
    cerr<<fixed<<setprecision(10);
    auto start = std::chrono::high_resolution_clock::now();
    int t=1;
    // cin>>t;
    while(t--) {
        solve();
    }
    auto stop = std::chrono::high_resolution_clock::now(); 
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start); 
    
    // cerr << "Time taken : " << ((long double)duration.count())/((long double) 1e9) <<"s "<< endl;     
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 526840 KB Output is correct
2 Correct 301 ms 526712 KB Output is correct
3 Correct 308 ms 526844 KB Output is correct
4 Correct 302 ms 526968 KB Output is correct
5 Correct 299 ms 526712 KB Output is correct
6 Correct 390 ms 526712 KB Output is correct
7 Correct 301 ms 526712 KB Output is correct
8 Correct 308 ms 526712 KB Output is correct
9 Correct 300 ms 526712 KB Output is correct
10 Correct 305 ms 526712 KB Output is correct
11 Correct 303 ms 526968 KB Output is correct
12 Correct 302 ms 526840 KB Output is correct
13 Correct 329 ms 526712 KB Output is correct
14 Correct 334 ms 526712 KB Output is correct
15 Correct 311 ms 526712 KB Output is correct
16 Correct 303 ms 526840 KB Output is correct
17 Correct 299 ms 526840 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 526840 KB Output is correct
2 Correct 301 ms 526712 KB Output is correct
3 Correct 308 ms 526844 KB Output is correct
4 Correct 302 ms 526968 KB Output is correct
5 Correct 299 ms 526712 KB Output is correct
6 Correct 390 ms 526712 KB Output is correct
7 Correct 301 ms 526712 KB Output is correct
8 Correct 308 ms 526712 KB Output is correct
9 Correct 300 ms 526712 KB Output is correct
10 Correct 305 ms 526712 KB Output is correct
11 Correct 303 ms 526968 KB Output is correct
12 Correct 302 ms 526840 KB Output is correct
13 Correct 329 ms 526712 KB Output is correct
14 Correct 334 ms 526712 KB Output is correct
15 Correct 311 ms 526712 KB Output is correct
16 Correct 303 ms 526840 KB Output is correct
17 Correct 299 ms 526840 KB Output is correct
18 Correct 297 ms 526712 KB Output is correct
19 Correct 326 ms 526816 KB Output is correct
20 Correct 303 ms 526720 KB Output is correct
21 Correct 310 ms 526832 KB Output is correct
22 Correct 305 ms 526756 KB Output is correct
23 Correct 302 ms 526840 KB Output is correct
24 Correct 301 ms 526712 KB Output is correct
25 Correct 299 ms 526688 KB Output is correct
26 Correct 289 ms 526840 KB Output is correct
27 Correct 284 ms 526712 KB Output is correct
28 Correct 284 ms 526840 KB Output is correct
29 Correct 293 ms 526712 KB Output is correct
30 Correct 295 ms 526712 KB Output is correct
31 Correct 285 ms 526712 KB Output is correct
32 Correct 298 ms 526840 KB Output is correct
33 Correct 295 ms 526968 KB Output is correct
34 Correct 292 ms 526804 KB Output is correct
35 Correct 301 ms 526712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 526840 KB Output is correct
2 Correct 301 ms 526712 KB Output is correct
3 Correct 308 ms 526844 KB Output is correct
4 Correct 302 ms 526968 KB Output is correct
5 Correct 299 ms 526712 KB Output is correct
6 Correct 390 ms 526712 KB Output is correct
7 Correct 301 ms 526712 KB Output is correct
8 Correct 308 ms 526712 KB Output is correct
9 Correct 300 ms 526712 KB Output is correct
10 Correct 305 ms 526712 KB Output is correct
11 Correct 303 ms 526968 KB Output is correct
12 Correct 302 ms 526840 KB Output is correct
13 Correct 329 ms 526712 KB Output is correct
14 Correct 334 ms 526712 KB Output is correct
15 Correct 311 ms 526712 KB Output is correct
16 Correct 303 ms 526840 KB Output is correct
17 Correct 299 ms 526840 KB Output is correct
18 Correct 307 ms 526712 KB Output is correct
19 Correct 299 ms 526840 KB Output is correct
20 Correct 308 ms 526712 KB Output is correct
21 Correct 301 ms 526840 KB Output is correct
22 Correct 317 ms 526912 KB Output is correct
23 Correct 293 ms 526712 KB Output is correct
24 Correct 292 ms 526716 KB Output is correct
25 Correct 311 ms 526840 KB Output is correct
26 Correct 296 ms 526816 KB Output is correct
27 Correct 298 ms 526712 KB Output is correct
28 Correct 297 ms 526712 KB Output is correct
29 Correct 307 ms 526712 KB Output is correct
30 Correct 298 ms 526712 KB Output is correct
31 Correct 298 ms 526712 KB Output is correct
32 Correct 291 ms 526712 KB Output is correct
33 Correct 307 ms 526712 KB Output is correct
34 Correct 290 ms 526840 KB Output is correct
35 Correct 300 ms 526908 KB Output is correct
36 Correct 298 ms 526712 KB Output is correct
37 Correct 301 ms 526712 KB Output is correct
38 Correct 292 ms 526712 KB Output is correct
39 Correct 295 ms 526712 KB Output is correct
40 Correct 298 ms 526840 KB Output is correct
41 Correct 325 ms 526712 KB Output is correct
42 Correct 305 ms 526840 KB Output is correct
43 Correct 329 ms 526712 KB Output is correct
44 Correct 310 ms 526736 KB Output is correct
45 Correct 317 ms 526712 KB Output is correct
46 Correct 305 ms 526844 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 526840 KB Output is correct
2 Correct 301 ms 526712 KB Output is correct
3 Correct 308 ms 526844 KB Output is correct
4 Correct 302 ms 526968 KB Output is correct
5 Correct 299 ms 526712 KB Output is correct
6 Correct 390 ms 526712 KB Output is correct
7 Correct 301 ms 526712 KB Output is correct
8 Correct 308 ms 526712 KB Output is correct
9 Correct 300 ms 526712 KB Output is correct
10 Correct 305 ms 526712 KB Output is correct
11 Correct 303 ms 526968 KB Output is correct
12 Correct 302 ms 526840 KB Output is correct
13 Correct 329 ms 526712 KB Output is correct
14 Correct 334 ms 526712 KB Output is correct
15 Correct 311 ms 526712 KB Output is correct
16 Correct 303 ms 526840 KB Output is correct
17 Correct 299 ms 526840 KB Output is correct
18 Correct 297 ms 526712 KB Output is correct
19 Correct 326 ms 526816 KB Output is correct
20 Correct 303 ms 526720 KB Output is correct
21 Correct 310 ms 526832 KB Output is correct
22 Correct 305 ms 526756 KB Output is correct
23 Correct 302 ms 526840 KB Output is correct
24 Correct 301 ms 526712 KB Output is correct
25 Correct 299 ms 526688 KB Output is correct
26 Correct 289 ms 526840 KB Output is correct
27 Correct 284 ms 526712 KB Output is correct
28 Correct 284 ms 526840 KB Output is correct
29 Correct 293 ms 526712 KB Output is correct
30 Correct 295 ms 526712 KB Output is correct
31 Correct 285 ms 526712 KB Output is correct
32 Correct 298 ms 526840 KB Output is correct
33 Correct 295 ms 526968 KB Output is correct
34 Correct 292 ms 526804 KB Output is correct
35 Correct 301 ms 526712 KB Output is correct
36 Correct 307 ms 526712 KB Output is correct
37 Correct 299 ms 526840 KB Output is correct
38 Correct 308 ms 526712 KB Output is correct
39 Correct 301 ms 526840 KB Output is correct
40 Correct 317 ms 526912 KB Output is correct
41 Correct 293 ms 526712 KB Output is correct
42 Correct 292 ms 526716 KB Output is correct
43 Correct 311 ms 526840 KB Output is correct
44 Correct 296 ms 526816 KB Output is correct
45 Correct 298 ms 526712 KB Output is correct
46 Correct 297 ms 526712 KB Output is correct
47 Correct 307 ms 526712 KB Output is correct
48 Correct 298 ms 526712 KB Output is correct
49 Correct 298 ms 526712 KB Output is correct
50 Correct 291 ms 526712 KB Output is correct
51 Correct 307 ms 526712 KB Output is correct
52 Correct 290 ms 526840 KB Output is correct
53 Correct 300 ms 526908 KB Output is correct
54 Correct 298 ms 526712 KB Output is correct
55 Correct 301 ms 526712 KB Output is correct
56 Correct 292 ms 526712 KB Output is correct
57 Correct 295 ms 526712 KB Output is correct
58 Correct 298 ms 526840 KB Output is correct
59 Correct 325 ms 526712 KB Output is correct
60 Correct 305 ms 526840 KB Output is correct
61 Correct 329 ms 526712 KB Output is correct
62 Correct 310 ms 526736 KB Output is correct
63 Correct 317 ms 526712 KB Output is correct
64 Correct 305 ms 526844 KB Output is correct
65 Correct 321 ms 526840 KB Output is correct
66 Correct 321 ms 526712 KB Output is correct
67 Correct 310 ms 526968 KB Output is correct
68 Correct 322 ms 526840 KB Output is correct
69 Correct 338 ms 526712 KB Output is correct
70 Correct 324 ms 526840 KB Output is correct
71 Correct 324 ms 526716 KB Output is correct
72 Correct 316 ms 526712 KB Output is correct
73 Correct 314 ms 526840 KB Output is correct
74 Correct 315 ms 526840 KB Output is correct
75 Correct 312 ms 526712 KB Output is correct
76 Correct 322 ms 526712 KB Output is correct
77 Correct 305 ms 526840 KB Output is correct
78 Correct 314 ms 526712 KB Output is correct
79 Correct 306 ms 526840 KB Output is correct
80 Correct 318 ms 526840 KB Output is correct
81 Correct 304 ms 526840 KB Output is correct
82 Correct 310 ms 526796 KB Output is correct
83 Correct 323 ms 526840 KB Output is correct
84 Correct 318 ms 526748 KB Output is correct
85 Correct 323 ms 526712 KB Output is correct
86 Correct 325 ms 526712 KB Output is correct
87 Correct 342 ms 526840 KB Output is correct
88 Correct 339 ms 526816 KB Output is correct
89 Correct 338 ms 526872 KB Output is correct
90 Correct 316 ms 526712 KB Output is correct
91 Correct 336 ms 526772 KB Output is correct
92 Correct 338 ms 526708 KB Output is correct
93 Correct 337 ms 526840 KB Output is correct