Submission #1172069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172069		SmuggingSpun	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	415 ms	135332 KiB

ho_t3

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
const int lim = 205;
int n, L, x[lim], t[lim];
namespace sub1{
    void solve(){
        vector<vector<bool>>dp(L + 1, vector<bool>(1 << n, false));
        dp[1][0] = true;
        auto fix = [&] (int time){
            for(int i = 1; i <= L; i++){
                for(int mask = (1 << n) - 1; mask > -1; mask--){
                    if(dp[i][mask]){
                        for(int j = 1; j <= n; j++){
                            if(x[j] == i && t[j] >= time){
                                dp[i][mask | (1 << (j - 1))] = true;
                                break;
                            }
                        }
                    }
                }
            }
        };
        fix(1);
        for(int time = 2; time < lim; time++){
            vector<vector<bool>>ndp(L + 1, vector<bool>(1 << n, false));
            for(int i = 1; i <= L; i++){
                for(int mask = (1 << n) - 1; mask > -1; mask--){
                    if(dp[i][mask]){
                        ndp[i == 1 ? L - 1 : i - 1][mask] = ndp[i == L - 1 ? 1 : i + 1][mask] = true;
                    }
                }
            }
            swap(dp, ndp);
            fix(time);
        }
        int ans = 0;
        for(int i = 1; i <= L; i++){
            for(int mask = (1 << n) - 1; mask > 0; mask--){
                if(dp[i][mask]){
                    maximize(ans, __builtin_popcount(mask));
                }
            }
        }
        cout << ans;
    }
}
namespace sub234{
    ll f[lim][lim][2][lim];
    ll dp(int l, int r, bool dir, int k){
        if(k == 0){
            return INF;
        }
        if(l > r){
            return -INF;
        }
        ll& ans = f[l][r][dir][k];
        if(ans != -1){
            return ans;
        }
        int current = (dir ? x[r + 1] : x[l - 1]), ld = abs(current - x[l]), rd = abs(current - x[r]);
        minimize(ld, L - ld);
        minimize(rd, L - rd);
        return ans = max({dp(l + 1, r, false, k) - ld, dp(l, r - 1, true, k) - rd, min(ll(t[l]), dp(l + 1, r, false, k - 1)) - ld, min(ll(t[r]), dp(l, r - 1, true, k - 1)) - rd});
    }
    void solve(){
        memset(f, -1, sizeof(f));
        x[n + 1] = 0;
        for(int i = n; i > 0; i--){
            if(dp(1, n, true, i) > -1){
                return void(cout << i);
            }
        }
        cout << 0;
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n >> L;
    for(int i = 1; i <= n; i++){
        cin >> x[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> t[i];
    }
    if(n <= 12 && L <= 200 && *max_element(t + 1, t + n + 1) <= 200){
        sub1::solve();
    }
    else{
        sub234::solve();
    }
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:92:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75