Submission #364787

#	Time	Username	Problem	Language	Result	Execution time	Memory
364787		cpp219	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	1877 ms	85404 KiB

ho_t3

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 200 + 3;
const ll inf = 1e9 + 7;
typedef pair<int,int> LL;

ll n,lens,a[N],dp[N][N][N][2],lim[N];
ll ans;
struct Node{
    ll val,L,R,p,lr;
};
bool operator < (Node a,Node b){
    return a.val > b.val;
}
priority_queue<Node> pq;

ll Ask(ll L,ll R){
    return lens - a[L] + a[R];
}

void Minimize(ll L,ll R,ll p,ll lr,ll val){
    if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
    //cout<<L<<" "<<R<<" "<<p<<" "<<lr<<"x\n";
    dp[L][R][p][lr] = val; pq.push({val,L,R,p,lr});
}

void process(ll L,ll R,ll p,ll lr){}

int 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);
    }
    cin>>n>>lens;
    for (ll i = 1;i <= n;i++) cin>>a[i];
    for (ll i = 1;i <= n;i++) cin>>lim[i];
    for (ll i = 0;i <= n;i++)
        for (ll j = 0;j <= n;j++)
            for (ll l = 0;l <= n;l++) dp[i][j][l][0] = dp[i][j][l][1] = inf;
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    pq.push({0,0,0,0,0}); pq.push({0,0,0,0,1});
    while(!pq.empty()){
        Node t = pq.top(); pq.pop();
        ll L = t.L,R = t.R,p = t.p,lr = t.lr,A = t.val,now1,now2;
        //cout<<L<<" "<<R<<" "<<p<<" "<<lr<<" x "<<A<<":\n";
        if (L - R == 1) continue;
        if (L == 0&&R == n) continue;
        ll nxtL = L - 1,nxtR = R + 1;
        if (!L) nxtL = n;
        if (!lr){
            now1 = A + a[L] - a[nxtL],now2 = A + Ask(L,R + 1);
            if (L == 0) now1 = A + lens - a[nxtL];
            //cout<<now1; return 0;
        }
        else{
            now1 = A + Ask(nxtL,R),now2 = A + a[R + 1] - a[R];
        }
        //cout<<now1<<" "<<lim[nxtL]; return 0;
        if (now1 <= lim[nxtL]) Minimize(nxtL,R,p + 1,0,now1);
        else Minimize(nxtL,R,p,0,now1);
        if (now2 <= lim[R + 1]) Minimize(L,R + 1,p + 1,1,now2);
        else Minimize(L,R + 1,p,1,now2); //cout<<"\n";
    }
    cout<<ans;
}

Compilation message (stderr)

ho_t3.cpp: In function 'void Minimize(int, int, int, int, int)':
ho_t3.cpp:26:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |     if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
      |     ^~
ho_t3.cpp:26:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |     if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
      |                                         ^~~
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:55:25: warning: unused variable 'nxtR' [-Wunused-variable]
   55 |         ll nxtL = L - 1,nxtR = R + 1;
      |                         ^~~~
ho_t3.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   38 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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