제출 #1279923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279923		enxiayy	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	63 ms	135304 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } 
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } 

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 205;

int n;
ll X[N], T[N], L;
ll dp[N][N][N][2]; // vis [L, R], get K stamps, 0/1 : cur_pos : L, R

ll get_dist(int l, int r) {
    ll u = X[l];
    ll v = X[r];
    return min(v - u, L - v + u);
}

void solve() {
    cin >> n >> L;
    FOR(i, 1, n) cin >> X[i];
    FOR(i, 1, n) cin >> T[i];

    

    memset(dp, 0x3f, sizeof(dp));
    ll inf = dp[0][0][0][0];
    dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;

    X[n + 1] = L;

    FOR(l, 0, n) {
        FORD(r, n + 1, l + 1) {
            FOR(k, 0, n) {
                FOR(dir, 0, 1) {     
                    if (dp[l][r][k][dir] == inf) continue;  
                    minimize(dp[l + 1][r][k][0], dp[l][r][k][dir] + (dir == 0 ? get_dist(l, l + 1) : get_dist(l + 1, r)));
                    minimize(dp[l][r - 1][k][1], dp[l][r][k][dir] + (dir == 0 ? get_dist(l, r - 1) : get_dist(r - 1, r)));
                    if (dp[l + 1][r][k][0] <= T[l + 1]) minimize(dp[l + 1][r][k + 1][0], dp[l + 1][r][k][0]);
                    if (dp[l][r - 1][k][1] <= T[r - 1]) minimize(dp[l][r - 1][k + 1][1], dp[l][r - 1][k][1]);
                }
            }
        }
    }

    // FOR(l, 0, n) {
    //     FOR(r, l, n + 1) {
    //         FOR(k, 0, n) {
    //             FOR(dir, 0, 1) {
    //                 cout << dbg(l) << " " << dbg(r) << " " << dbg(k) << " " << dbg(dir) << el;
    //                 cout << dbg(dp[l][r][k][dir]) << el;
    //             }
    //         }
    //     }
    // }

    

    FORD(k, n, 0) {
        FOR(l, 0, n) {
            FOR(r, l + 1, n + 1) {
                FOR(dir, 0, 1) {
                    if (dp[l][r][k][dir] < inf) {
                        cout << k << el;
                        return;
                    }
                }
            }
        }
    }

    cout  << 0 << el;

    

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

컴파일 시 표준 에러 (stderr) 메시지

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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