oj.uz

Submission #996905

# Submission time Handle Problem Language Result Execution time Memory
996905 2024-06-11T12:15:39 Z irmuun Collecting Stamps 3 (JOI20_ho_t3) C++17
5 / 100
 2000 ms 1048584 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

//try
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,L;
    cin>>n>>L;
    ll x[n+5],t[n+5];
    for(ll i=1;i<=n;i++){
        cin>>x[i];
    }
    for(ll i=1;i<=n;i++){
        cin>>t[i];
    }
    x[0]=0;
    function <ll(ll,ll)> dist=[&](ll a,ll b){
        return min(abs(x[a]-x[b]),L-abs(x[a]-x[b]));
    };
    ll dp[1<<n][n+5][405];
    memset(dp,-1,sizeof dp);
    dp[0][0][0]=0;
    for(ll s=0;s<(1<<n);s++){
        for(ll i=0;i<=n;i++){
            if(i==0||(s&(1<<(i-1)))){
                for(ll T=0;T<=200;T++){
                    if(dp[s][i][T]==-1) continue;
                    for(ll j=0;j<n;j++){//next pos
                        if((s&(1<<j))==0){//currently not stamped j
                            chmax(dp[s|(1<<j)][j+1][T+dist(i,j+1)],dp[s][i][T]+(T+dist(i,j+1)<=t[j+1]));
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for(ll s=0;s<(1<<n);s++){
        for(ll i=1;i<=n;i++){
            for(ll T=0;T<=200;T++){
                ans=max(ans,dp[s][i][T]);
            }
        }
    }
    cout<<ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 19 ms 23048 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 157 ms 221132 KB Output is correct
7 Correct 6 ms 10840 KB Output is correct
8 Correct 36 ms 48988 KB Output is correct
9 Correct 151 ms 221172 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 171 ms 220968 KB Output is correct
13 Correct 147 ms 221008 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 7 ms 10840 KB Output is correct
16 Correct 156 ms 221200 KB Output is correct
17 Correct 161 ms 221012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 19 ms 23048 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 157 ms 221132 KB Output is correct
7 Correct 6 ms 10840 KB Output is correct
8 Correct 36 ms 48988 KB Output is correct
9 Correct 151 ms 221172 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 171 ms 220968 KB Output is correct
13 Correct 147 ms 221008 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 7 ms 10840 KB Output is correct
16 Correct 156 ms 221200 KB Output is correct
17 Correct 161 ms 221012 KB Output is correct
18 Execution timed out 2749 ms 1048584 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 19 ms 23048 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 157 ms 221132 KB Output is correct
7 Correct 6 ms 10840 KB Output is correct
8 Correct 36 ms 48988 KB Output is correct
9 Correct 151 ms 221172 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 171 ms 220968 KB Output is correct
13 Correct 147 ms 221008 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 7 ms 10840 KB Output is correct
16 Correct 156 ms 221200 KB Output is correct
17 Correct 161 ms 221012 KB Output is correct
18 Runtime error 473 ms 1048576 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1220 KB Output is correct
3 Correct 19 ms 23048 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 157 ms 221132 KB Output is correct
7 Correct 6 ms 10840 KB Output is correct
8 Correct 36 ms 48988 KB Output is correct
9 Correct 151 ms 221172 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 171 ms 220968 KB Output is correct
13 Correct 147 ms 221008 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 7 ms 10840 KB Output is correct
16 Correct 156 ms 221200 KB Output is correct
17 Correct 161 ms 221012 KB Output is correct
18 Execution timed out 2749 ms 1048584 KB Time limit exceeded
19 Halted 0 ms 0 KB -