제출 #747769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747769		prairie2022	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	0 ms	340 KiB

ho_t3

#include <bits/stdc++.h>
typedef long long ll;
#define int long long
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define F first 
#define S second
#define vst vis[tmp.w[0]][tmp.w[1]][tmp.b]
using namespace std;

const int M = 1e9;
int n, L, ans=0;
int x[2][201], d[2][201];
int vis[201][201][2] = {-1};

struct dp{
    int t, c, w[2];
    bool b;
    inline bool forward(){
        if(w[0]+w[1]==n) return 0;
        w[b]++;
        t += x[b][w[b]]-x[b][w[b]-1];
        //if(t>M) return 0;
        if(t<=d[b][w[b]]) c++;
        return 1;
    }
    inline bool backward(){
        if(w[0]+w[1]==n) return 0;
        b = !b;
        w[b]++;
        t += x[b][w[b]]+x[!b][w[!b]];
        //if(t>M) return 0;
        if(t<=d[b][w[b]]) c++;
        return 1;
    }
};

inline bool cmp(dp dp1, dp dp2){
    return dp1.t > dp2.t;
}

priority_queue<dp, vector<dp>, decltype(&cmp)> pq(cmp);

main(){
    dp tmp, ins;
    fastio
    //informations
    cin >> n >> L;
    x[0][0] = x[0][1] = 0;
    for(int i=1; i<=n; i++){
        cin >> x[0][i];
        x[1][n+1-i] = L-x[0][i];
    }
    for(int i=1; i<=n; i++){
        cin >> d[0][i];
        d[1][n+1-i] = d[0][i];
    }
    //dp
    pq.push({0, 0, {0, 0}, 0});
    while(!pq.empty() && pq.top().t<=M){
        tmp = pq.top();
        pq.pop();
        //cout << tmp.t << ' ' << tmp.c << ' ' << tmp.w[0] << ' ' << tmp.w[1] << (int)tmp.b << '\n';
        if(tmp.c<=vst) continue;
        vst = tmp.c;
        ans = max(ans, tmp.c);
        ins = tmp;
        if(ins.forward()) pq.push(ins);
        ins = tmp;
        if(ins.backward()) pq.push(ins);
    }
    cout << ans << '\n';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t3.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

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