Submission #1363894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363894		dex111222333444555	Collecting Stamps 3 (JOI20_ho_t3)	C++20	25 / 100	81 ms	135308 KiB

ho_t3

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define dbg(x) "[" #x " = " << x << "]"

using namespace std;

const long long inf = 1e18 + 132;

template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}

const int MAXN = 205;

int numVal, lenPath, val[MAXN], req[MAXN];
long long f[MAXN][MAXN][MAXN][2];

void input(){
    cin >> numVal >> lenPath;
    for(int i = 1; i <= numVal; i++) cin >> val[i];
    for(int i = 1; i <= numVal; i++) cin >> req[i];
    ++numVal;
}

int dist(int x, int y){
    int dA = (val[x] - val[y]), dB = (val[y] - val[x]);
    if (dA < 0) dA += lenPath;
    if (dB < 0) dB += lenPath;
    return min(dA, dB);
}

void solve(){
    int res = 0;

    memset(f, 0x3f, sizeof f);
    f[0][numVal][0][0] = f[0][numVal][0][1] = 0;

    for(int pre = 0; pre <= numVal; pre++){
        for(int suf = numVal; suf > pre; suf--){
            for(int num = 0; num <= numVal; num++){
                for(int flag = 0; flag < 2; flag++) if (f[pre][suf][num][flag] < inf){
                    res = max(res, num);

                    if (pre + 1 == suf) continue;

                    int distPre = dist(pre + 1, (!flag ? pre: suf)) + f[pre][suf][num][flag];
                    int distSuf = dist(suf - 1, (!flag ? pre: suf)) + f[pre][suf][num][flag];

                    minimize(f[pre + 1][suf][num][0], distPre);
                    minimize(f[pre][suf - 1][num][1], distSuf);

                    if (distPre <= req[pre + 1])
                        minimize(f[pre + 1][suf][num + 1][0], distPre);

                    if (distSuf <= req[suf - 1])
                        minimize(f[pre][suf - 1][num + 1][1], distSuf);
                }
            }
        }
    }

    cout << res << '\n';
    cerr << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while(t--){
        input();
        solve();
    }
    cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:74:16: 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:16: 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: 0 / 75