제출 #234739

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

ho_t3

#include <bits/stdc++.h>
#define DIM 210
#define INF 2000000000000000000LL
using namespace std;

pair <int,long long> dp[DIM][DIM][2];
int viz[DIM][DIM][2],v[DIM],t[DIM];
struct idk{
    int i,j,dir;
};
deque <idk> c;
int n,L,i,j;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>L;
    for (i=1;i<=n;i++)
        cin>>v[i];
    for (i=1;i<=n;i++)
        cin>>t[i];

    for (i=0;i<=n;i++)
        for (j=0;j<=n;j++)
            dp[i][j][0] = dp[i][j][1] = make_pair (0,INF);

    /// dp[i][j][0/1] - nr maxim de timbre pe care le pot lua daca am parcurs i din stanga si j din dreapta

    dp[0][0][0] = dp[0][0][1] = make_pair (0,0);
    c.push_back({0,0,0});
    viz[0][0][0] = 1;
    c.push_back({0,0,1});
    viz[0][0][1] = 1;

    while (!c.empty()){
        int i = c.front().i;
        int j = c.front().j;
        int dir = c.front().dir;
        c.pop_front();
        viz[i][j][dir] = 0;

        long long timp = dp[i][j][dir].second + L - v[n-j+1] + v[i];

        if (dir == 1){

            int cnt = 0;
            for (int poz=i+1;poz+j<=n;poz++){
                timp += v[poz] - v[poz-1];
                if (timp <= t[poz]){ /// as putea sa iau timbrul asta
                    cnt++;
                    if (dp[i][j][dir].first + cnt > dp[poz][j][0].first){
                        dp[poz][j][0].first = dp[i][j][dir].first + cnt;
                        dp[poz][j][0].second = timp;

                    } else {
                        if (dp[i][j][dir].first + cnt == dp[poz][j][0].first && timp < dp[poz][j][0].second)
                            dp[poz][j][0].second = timp;
                    }

                    if (dp[i][j][dir].first + cnt == dp[poz][j][0].first && !viz[poz][j][0]){
                        c.push_back({poz,j,0});
                        viz[poz][j][0] = 1;
                    }}}

        } else {
            int cnt = 0;
            for (int poz=j+1;i+poz<=n;poz++){

                timp += v[n-poz+2] - v[n-poz+1];
                if (timp <= t[n-poz+1]){
                    cnt++;
                    if (dp[i][j][dir].first + cnt > dp[i][poz][1].first){
                        dp[i][poz][1].first = dp[i][j][dir].first + cnt;
                        dp[i][poz][1].second = timp;
                    } else {
                        if (dp[i][j][dir].first + cnt == dp[i][poz][1].first && timp < dp[i][poz][1].second)
                            dp[i][poz][1].second = timp;
                    }

                    if (dp[i][j][dir].first + cnt == dp[i][poz][1].first && !viz[i][poz][1]){
                        c.push_back({i,poz,1});
                        viz[i][poz][1] = 1;
                    }}}}}

    int sol = 0;
    for (i=0;i<=n;i++)
        for (j=0;j<=n;j++)
            sol = max (sol,max(dp[i][j][0].first,dp[i][j][1].first));
    cout<<sol;

    return 0;
}

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