Submission #1219341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219341		CodeLakVN	Collecting Stamps 3 (JOI20_ho_t3)	C++20	15 / 100	1 ms	1604 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define li pair<long long, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)2e2 + 4;
const long long INF = (long long)1e18 + 1408;

int n, l;
long long pos[MAX_N];
int timeLimit[MAX_N];

namespace sub2 {
    li dp[1 << 15][20];
    
    long long dist(long long x, long long y) {
        if (x > y) swap(x, y);
        return min(y - x, x + l - y);
    }

    void solve() {
        FOR(mask, 1, (1 << n) - 1) {
            FOR(i, 0, n - 1) {
                dp[mask][i] = {INF, 0};
                if (!((mask >> i) & 1)) continue;
                if (__builtin_popcount(mask) == 1) {
                    dp[mask][i].F = dist(0, pos[i + 1]);
                    if (dp[mask][i].F <= timeLimit[i + 1]) dp[mask][i].S = 1;
                    continue;
                }
                int preMask = (mask ^ (1 << i));
                FOR(last, 0, n - 1) {
                    if (!((preMask >> last) & 1)) continue;
                    long long tmp = dp[preMask][last].F + dist(pos[last + 1], pos[i + 1]);
                    if (tmp <= timeLimit[i + 1]) {
                        if (dp[preMask][last].S + 1 > dp[mask][i].S)
                            dp[mask][i] = {tmp, dp[preMask][last].S + 1};
                        else if (dp[preMask][last].S + 1 == dp[mask][i].S)
                            dp[mask][i].F = min(dp[mask][i].F, tmp);
                    }
                }
            }
        }
        int ans = 0;
        FOR(mask, 1, (1 << n) - 1) FOR(i, 0, n - 1) ans = max(ans, dp[mask][i].S);

        cout << ans << "\n";
    }
}

namespace subFull {
    li dp[MAX_N][MAX_N][2]; 

    long long dist(long long x, long long y) {
        if (x > y) swap(x, y);
        return min(y - x, x + l - y);
    }

    void update(li &A, li B, long long newDist, int limit) {
        if (newDist <= limit) {
            if (B.S + 1 > A.S) A = {newDist, B.S + 1};
            else if (B.S + 1 == A.S && newDist < A.F) A.F = newDist; 
        }
        else {
            if (B.S > A.S) A = {newDist, B.S};
            else if (B.S == A.S && newDist < A.F) A.F = newDist;
        }
    }

    void solve() {
        FOR(i, 0, n + 1) FOR(j, 0, n + 1) FOR(k, 0, 1) dp[i][j][k] = {INF, 0};
        dp[0][n + 1][0] = dp[0][n + 1][1] = {0, 0};
        FOR(i, 0, n) FOD(j, n + 1, i + 1) {
            if (dp[i][j][0].F < INF) {
                if (i + 1 < j) {
                    long long newDist = dp[i][j][0].F + dist(pos[i], pos[i + 1]);
                    update(dp[i + 1][j][0], dp[i][j][0], newDist, timeLimit[i + 1]);
                }
                if (j - 1 > i) {
                    long long newDist = dp[i][j][0].F + dist(pos[i], pos[j - 1]);
                    update(dp[i][j - 1][1], dp[i][j][0], newDist, timeLimit[j - 1]);
                }
            }
            if (dp[i][j][1].F < INF) {
                if (i + 1 < j) {
                    long long newDist = dp[i][j][1].F + dist(pos[j], pos[i + 1]);
                    update(dp[i + 1][j][0], dp[i][j][1], newDist, timeLimit[i + 1]);
                }
                if (j - 1 > i) {
                    long long newDist = dp[i][j][1].F + dist(pos[j], pos[j - 1]);
                    update(dp[i][j - 1][1], dp[i][j][1], newDist, timeLimit[j - 1]);
                }
            }
        }

        int ans = 0;
        FOR(i, 0, n) FOR(j, 0, n) FOR(k, 0, 1) ans = max(ans, dp[i][j][k].S);
        cout << ans << "\n";
    }
}

void solve() {
    cin >> n >> l;
    FOR(i, 1, n) cin >> pos[i];
    FOR(i, 1, n) cin >> timeLimit[i];
    
    // if (n <= 15) sub2::solve();
    subFull::solve();
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

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

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