Submission #219599

#	Time	Username	Problem	Language	Result	Execution time	Memory
219599		MKopchev	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	1634 ms	41560 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)
{
    //cout<<"making "<<t<<" "<<l_now<<" "<<r_now<<" "<<ok<<" "<<side<<endl;

    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);

        //cout<<t_now<<" "<<l_now<<" "<<r_now<<" "<<satisfied<<" "<<side<<" "<<location<<endl;

        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+1>r_now-1)continue;

        if(t_now>MX_valid)continue;
        //go to l_now
        make_state(t_now+calc_dist(where[location],where[l_now+1]),l_now+1,r_now,satisfied+(t_now+calc_dist(where[location],where[l_now+1])<=t_max[l_now+1]),0);
        //go to r_now
        make_state(t_now+calc_dist(where[location],where[r_now-1]),l_now,r_now-1,satisfied+(t_now+calc_dist(where[location],where[r_now-1])<=t_max[r_now-1]),1);

        //cout<<"---"<<endl;
    }
    printf("%i\n",output);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:25: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:26: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:27: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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75