Submission #219592

#	Time	Username	Problem	Language	Result	Execution time	Memory
219592		MKopchev	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	5 ms	384 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e2+5;
int n,circle;
int where[nmax],t_max[nmax];

int dp[nmax][nmax][nmax][2];//min time to get to state left position, right position, satisfied stamps, on left/right

priority_queue< pair< pair< pair< pair<int/*time*/,int/*left position*/>,int/*right position*/>,int/*satisfied*/>,int/*on left/right*/> > pq;

int calc_dist(int a,int b)
{
    int ret=abs(a-b);
    return min(ret,circle-ret);
}

void make_state(int t,int l_now,int r_now,int ok,bool side)
{
    pq.push({{{{-t,l_now},r_now},ok},side});
}
int main()
{
    scanf("%i%i",&n,&circle);
    for(int i=1;i<=n;i++)scanf("%i",&where[i]);
    for(int i=1;i<=n;i++)scanf("%i",&t_max[i]);

    int MX_valid=0;
    for(int i=1;i<=n;i++)MX_valid=max(MX_valid,t_max[i]);

    //go to 1
    make_state(calc_dist(0,where[1]),1,n+1,calc_dist(0,where[1])<=t_max[1],0);

    //go to n
    make_state(calc_dist(0,where[n]),0,n,calc_dist(0,where[n])<=t_max[n],1);

    int output=0;
    while(pq.size())
    {
        pair< pair< pair< pair<int/*time*/,int/*left position*/>,int/*right position*/>,int/*satisfied*/>,int/*on left/right*/> use=pq.top();
        pq.pop();

        int t_now=-use.first.first.first.first;
        int l_now=use.first.first.first.second;
        int r_now=use.first.first.second;
        int satisfied=use.first.second;
        bool side=use.second;
        int location=(side==0?l_now:r_now);

        output=max(output,satisfied);

        if(dp[l_now][r_now][satisfied][side])continue;
        dp[l_now][r_now][satisfied][side]=t_now;

        //[l_now+1...r_now-1] are remaining
        if(l_now==r_now)continue;

        if(t_now>MX_valid)continue;
        //go to l_now
        make_state(t_now+calc_dist(location,where[l_now+1]),l_now+1,r_now,satisfied+(t_now+calc_dist(location,where[l_now+1])<=t_max[l_now+1]),0);
        //go to r_now
        make_state(t_now+calc_dist(location,where[r_now-1]),l_now,r_now-1,satisfied+(t_now+calc_dist(location,where[r_now-1])<=t_max[r_now-1]),1);
    }
    printf("%i\n",output);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&circle);
     ~~~~~^~~~~~~~~~~~~~~~~~~
ho_t3.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&where[i]);
                          ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:25:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&t_max[i]);
                          ~~~~~^~~~~~~~~~~~~~~~

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