Submission #1265114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265114		lmaobruh	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	307 ms	509108 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define ve vector
#define all(x) x.begin(), x.end()
#define fo(i,a,b) for (int i=(a),_b=(b); i<=_b; ++i)
#define fd(i,a,b) for (int i=(a),_b=(b); i>=_b; --i)
#define maxi(a, b) a = max(a, b)
#define mini(a, b) a = min(a, b)

const int N = 402, inf = 1e9+10, mod = 1e9+7;

/*
    f[i][j][k][l] : min time de di tu i->j, lay duoc k tem, l=(0/1:trai phai)
*/

int f[N][N][N][2], n, l, x[N*2], t[N*2];

int mr(int x, int y) {
    return x + l - y;
}

int op(int x, int y) {
    return min({abs(x-y),mr(x,y),mr(y,x)});
}

void sol() {
    cin >> n >> l;
    fo(i,1,n) cin >> x[i], x[i+n+1]=x[i];
    fo(i,1,n) cin >> t[i], t[i+n+1]=t[i];
    x[n+1]=0, t[n+1]=-1;
    memset(f,0x3f,sizeof(f));
    f[n+1][n+1][0][0]=f[n+1][n+1][0][1]=0;
    // tu 1 den 2*n+1
    int m=2*n+1, ans=0;
    fo(len,2,n+1) {
        fo(l,1,m-len+1) fo(k,0,len-1) {
            int r=l+len-1;
            int ldp=f[l+1][r][k][0];
            int ti=ldp+op(x[l+1],x[l]);
            mini(f[l][r][k+(ti<=t[l])][0],ti);
            
            ldp=f[l+1][r][k][1];
            ti=ldp+op(x[l],x[r]);
            mini(f[l][r][k+(ti<=t[l])][0],ti);
            
            int rdp=f[l][r-1][k][1];
            ti=rdp+op(x[r-1],x[r]);
            mini(f[l][r][k+(ti<=t[r])][1],ti);
            
            rdp=f[l][r-1][k][0];
            ti=rdp+op(x[r],x[l]);
            mini(f[l][r][k+(ti<=t[r])][1],ti);
        }
    }
    fo(len,1,n+1) fo(l,1,m-len+1) fo(k,0,len) if (f[l][l+len-1][k][0]<=inf||f[l][l+len-1][k][1]<=inf) maxi(ans,k);
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    if(fopen("A.inp","r")) {
        freopen("A.inp","r",stdin);
        freopen("A.out","w",stdout);
    }
    int tc = 1; // cin >> tc;
    fo(i,1,tc) sol();
    return 0;
}

Compilation message (stderr)

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

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