oj.uz

Submission #680966

# Submission time Handle Problem Language Result Execution time Memory
680966 2023-01-12T06:59:08 Z Tuanlinh123 Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 852 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
 
using namespace std;
 
#define LOCALIO "C:/Users/admin/Documents/Code/"
 
const ll INF=1000000005;
ll n, L, a[205], t[205], res;
ll dp[205][205][205][2];
bool check[205][205][205][2];
 
ll dis(ll l, ll r, ll di)
{
    if (!di)
    {
        if (r<l)
            return a[r]-a[l]+L;
        return a[r]-a[l];
    }
    if (r>l)
        return a[l]-a[r]+L;
    return a[l]-a[r];
}
 
ll calc(ll l, ll r, ll k, ll di)
{
    if (k<0) return INF;
    if (check[l][r][k][di])
        return dp[l][r][k][di];
    if (l==r) 
        return dp[l][r][k][di];
    ll ans=INF;
    if (!di)
    {
        ll A=calc((l+1)%n, r, k-1, 0);
        ll B=calc((l+1)%n, r, k, 0);
        ll C=calc((l+1)%n, r, k-1, 1);
        ll D=calc((l+1)%n, r, k, 1);
        ll dis1=dis((l+1)%n, l, 1), dis2=dis(r, l, 1);
        if (t[l]>=A+dis1)
            ans=min(ans, A+dis1);
        if (t[l]<B+dis1)
            ans=min(ans, B+dis1);
        if (t[l]>=C+dis2)
            ans=min(ans, C+dis2);
        if (t[l]<D+dis2)
            ans=min(ans, D+dis2);
    }
    else
    {
        ll A=calc(l, (r-1+n)%n, k-1, 0);
        ll B=calc(l, (r-1+n)%n, k, 0);
        ll C=calc(l, (r-1+n)%n, k-1, 1);
        ll D=calc(l, (r-1+n)%n, k, 1);
        ll dis1=dis((r-1+n)%n, r, 0), dis2=dis(l, r, 0);
        if (t[r]>=A+dis2)
            ans=min(ans, A+dis2);
        if (t[r]<B+dis2)
            ans=min(ans, B+dis2);
        if (t[r]>=C+dis1)
            ans=min(ans, C+dis1);
        if (t[r]<D+dis1)
            ans=min(ans, D+dis1);
    }
    dp[l][r][k][di]=ans;
    check[l][r][k][di]=1;
    // if (ans!=INF)
        // cout << l << " " << r << " " << k << " " << di << " " << ans << "\n";
    if (l==(r+1)%n && ans!=INF)
        res=max(res, k);
    return ans;
}
 
int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif
 
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n >> L;
    for (ll i=0; i<n; i++)
        cin >> a[i];
    for (ll i=0; i<n; i++)
        cin >> t[i];
    for (ll i=0; i<n; i++)
        for (ll j=0; j<n; j++)
            for (ll k=0; k<=n; k++)
                for (ll di=0; di<2; di++)
                    dp[i][j][k][di]=INF;
    dp[0][0][t[0]>=a[0]][0]=a[0];
    dp[n-1][n-1][t[n-1]>=L-a[n-1]][0]=L-a[n-1];
    for (ll i=0; i<n; i++)
        for (ll k=0; k<=n; k++)
            calc((i+1)%n, i, k, 0), calc((i+1)%n, i, k, 1);
    cout << res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -