Submission #807382

#	Time	Username	Problem	Language	Result	Execution time	Memory
807382		vjudge1	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	111 ms	145408 KiB

ho_t3

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

// clang-format off

#define           fi    first
#define           se    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int32_t)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define         left    Kurumi_Tokisaki
#define        right    Kei_Karuizawa
#define         next    Mai_Sakurajima
#define          div    Yume_Irido
#define         prev    Chizuru_Mizuhara
#define    cntbit(x)    __builtin_popcountll(x)
#define      MASK(x)    ( 1ll << (x) )
#define          Yes    cout << "Yes"
#define          YES    cout << "YES"
#define           No    cout << "No"
#define           NO    cout << "NO"
#define           AA    cout << "Alice"
#define           BB    cout << "Bob"

/// TASK
/// -----------------------------
#ifdef LMQZZZ
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << " ]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define deb(x...) cerr << "[ in " <<__func__<< "() : line " <<__LINE__<< " ] : [ " << #x << " ] = [ "; _print(x); cerr << '\n';
#define TASK "C"
#else
#define deb(x...) 3326
#define TASK "C"
#endif
///------------------------------

void lmqzzz();
void init() {};
int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);      cout.tie(0);
        if (fopen(TASK ".inp", "r")) {
                freopen(TASK ".inp", "r", stdin);
                freopen(TASK ".out", "w", stdout);
        }
        /// =================================
                constexpr bool MULTITEST = 0;
        /// ================================
        init();
        int32_t TT = 1;
        if ( MULTITEST ) cin >> TT;
        for(int32_t TTT = 1; TTT <= TT; TTT ++) {
                lmqzzz();
                cout << '\n';
        }
}

template <class T> inline T min(const T &a, const T &b, const T &c) { return min(a, min(b, c)); }
template <class T> inline T max(const T &a, const T &b, const T &c) { return max(a, max(b, c)); }
template <class T, class U> inline bool mini(T &a, const U &b) { if (a > b) { a = b; return 1; } return 0; }
template <class T, class U> inline bool maxi(T &a, const U &b) { if (a < b) { a = b; return 1; } return 0; }

constexpr     int16_t dr[]  =  {0, 0, -1, 1};
constexpr     int16_t dc[]  =  {1, -1, 0, 0};
constexpr      int64_t MOD  =  1e9 + 7;
constexpr     int32_t MAXN  =  2e2 + 10;

// clang-format on

int n, m;
int a[MAXN], b[MAXN];
int64_t f[MAXN][MAXN][MAXN][2];

void lmqzzz() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        n++;
        memset(f, 0x3f, sizeof f);

        auto dist = [=](int x, int y) {
                if (x > y) swap(x, y);
                return min(a[y] - a[x], m - (a[y] - a[x]));
        };

        f[0][0][0][0] = 0;
        for (int d = 0; d < n; d++) {
                for (int l = 0, r = l + d; l < n; l++, r = (r + 1) % n) {
                        for (int cur = 0; cur <= d; cur++) {
                                for (int z = 0; z < 2; z++) {
                                        if (f[l][r][cur][z] < 1e18) {
                                                int64_t time = f[l][r][cur][z];
                                                int ll = (l + n - 1) % n;
                                                int rr = (r + 1) % n;
                                                int64_t cl = time + dist(z ? r : l, ll);
                                                int64_t cr = time + dist(z ? r : l, rr);
                                                if (ll != r) mini(f[ll][r][cur + (cl <= b[ll])][0], cl);
                                                if (l != rr) mini(f[l][rr][cur + (cr <= b[rr])][1], cr);
                                        }
                                }
                        }
                }
        }
        int res = 0;
        for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                        for (int k = 0; k <= n; k++) {
                                for (int z = 0; z < 2; z++) {
                                        if (f[i][j][k][z] < 1e18) {
                                                res = max(res, k);
                                        }
                                }
                        }
                }
        }
        cout << res;
}

Compilation message (stderr)

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

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