oj.uz

답안 #219590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219590 2020-04-05T16:29:05 Z MKopchev Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 5 ms 384 KB 
#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);
}

pair< pair< pair< pair<int/*time*/,int/*left position*/>,int/*right position*/>,int/*satisfied*/>,int/*on left/right*/> 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

ho_t3.cpp: In function 'std::pair<std::pair<std::pair<std::pair<int, int>, int>, int>, int> make_state(int, int, int, int, bool)':
ho_t3.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -