oj.uz

Submission #959248

# Submission time Handle Problem Language Result Execution time Memory
959248 2024-04-07T18:07:29 Z AndreiBOTO Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 137 ms 444756 KB 
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

///What a day...
///You look lonely, I can fix that

const long long INF=1e13;
const int NMAX=305;

#define int long long

int dp[NMAX][NMAX][NMAX][2];        ///minimum time -> clock, counter-clock, answer, direction (0->clock, 1->counter-clock)
int x[NMAX];
int t[NMAX];
int l;

int get_dist(int a,int b)
{
    ///I got guns in my head and they won't go,
    ///Spirits in my head and they won't go...

    if(a==b)
        return 0;
    else
    {
        if(a>b)
            swap(a,b);
        return min(x[b]-x[a],l-x[b]+x[a]);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,i,j,k,st,dr,best=0,ans;
    cin>>n>>l;
    for(i=1;i<=n;i++)
        cin>>x[i];
    x[0]=0;
    x[n+1]=l;
    for(i=1;i<=n;i++)
        cin>>t[i];
    t[0]=-10;
    t[n+1]=-10;
    /*for(i=0;i<=n+1;i++)
        for(j=0;j<=n+1;j++)
            for(k=0;k<=n+1;k++)
                dp[i][j][k][0]=dp[i][j][k][1]=INF;*/
    memset(dp,63,sizeof(dp));
    dp[0][0][0][0]=dp[0][0][0][1]=0;
    for(st=0;st<=n;st++)
    {
        for(dr=0;dr<=n;dr++)
        {
            if(st+dr>n)
                break;
            for(ans=0;ans<=n;ans++)
            {
                if(min(dp[st][dr][ans][0],dp[st][dr][ans][1])<INF)
                    best=max(best,ans);
                if(st+1<=n)
                {
                    int auxy=dp[st][dr][ans][0]+get_dist(st,st+1);
                    auxy=min(auxy,dp[st][dr][ans][1]+get_dist(n+1-dr,st+1));
                    if(auxy<=t[st+1])
                    {
                        dp[st+1][dr][ans+1][0]=min(dp[st+1][dr][ans+1][0],auxy);
                        //best=max(best,ans+1);
                    }
                    else
                        dp[st+1][dr][ans][0]=min(dp[st+1][dr][ans][0],auxy);
                }
                if(dr+1<=n)
                {
                    int auxy=dp[st][dr][ans][1]+get_dist(n+1-dr,n+1-dr-1);
                    auxy=min(auxy,dp[st][dr][ans][0]+get_dist(dr,n+1-dr-1));
                    if(auxy<=t[n+1-dr-1])
                    {
                        dp[st][dr+1][ans+1][1]=min(dp[st][dr+1][ans+1][1],auxy);
                        //best=max(best,ans+1);
                    }
                    else
                        dp[st][dr+1][ans][1]=min(dp[st][dr+1][ans][1],auxy);
                }
            }
        }
    }
    cout<<best<<"\n";
    return 0;
}

Compilation message

ho_t3.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:46:13: warning: unused variable 'j' [-Wunused-variable]
   46 |     int n,i,j,k,st,dr,best=0,ans;
      |             ^
ho_t3.cpp:46:15: warning: unused variable 'k' [-Wunused-variable]
   46 |     int n,i,j,k,st,dr,best=0,ans;
      |               ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 444556 KB Output is correct
2 Correct 124 ms 444496 KB Output is correct
3 Correct 137 ms 444456 KB Output is correct
4 Correct 127 ms 444496 KB Output is correct
5 Correct 124 ms 444612 KB Output is correct
6 Correct 123 ms 444496 KB Output is correct
7 Incorrect 128 ms 444756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 444556 KB Output is correct
2 Correct 124 ms 444496 KB Output is correct
3 Correct 137 ms 444456 KB Output is correct
4 Correct 127 ms 444496 KB Output is correct
5 Correct 124 ms 444612 KB Output is correct
6 Correct 123 ms 444496 KB Output is correct
7 Incorrect 128 ms 444756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 444556 KB Output is correct
2 Correct 124 ms 444496 KB Output is correct
3 Correct 137 ms 444456 KB Output is correct
4 Correct 127 ms 444496 KB Output is correct
5 Correct 124 ms 444612 KB Output is correct
6 Correct 123 ms 444496 KB Output is correct
7 Incorrect 128 ms 444756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 444556 KB Output is correct
2 Correct 124 ms 444496 KB Output is correct
3 Correct 137 ms 444456 KB Output is correct
4 Correct 127 ms 444496 KB Output is correct
5 Correct 124 ms 444612 KB Output is correct
6 Correct 123 ms 444496 KB Output is correct
7 Incorrect 128 ms 444756 KB Output isn't correct
8 Halted 0 ms 0 KB -