oj.uz

Submission #211448

# Submission time Handle Problem Language Result Execution time Memory
211448 2020-03-20T11:11:24 Z mayhoubsaleh Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 139 ms 262148 KB 
/*#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const int inf=1e9+10;
const int maxn=1e6+100;

int n,s,k;
int nxt[maxn][20],pos[maxn],pre[maxn];
int sh[maxn];
int main()
{
    IOS
    cin>>n>>s>>k;
    pos[1]=0;
    for(int i=2;i<=n;i++){
        cin>>pos[i];
        pos[i]+=pos[i-1];
    }
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        pre[i]+=pre[i-1];
        //cout<<pre[i]<<' ';
    }
    pre[n+1]=pre[n];
    for(int i=1;i<=n;i++){
        int id=upper_bound(pos+i,pos+n+1,pos[i]+k)-pos;
        id--;
        sh[i]=id;
        nxt[i][0]=upper_bound(pos+id,pos+n+1,pos[id]+k)-pos;
        //cout<<nxt[i][0]<<' ';
    }

    for(int i=1;i<20;i++){
        for(int id=1;id<=n;id++){
            nxt[id][i]=nxt[nxt[id][i-1]][i-1];
            if(!nxt[id][i])nxt[id][i]=n+1;
        }
    }
    pair<int,int>mx={-1,-1};
    for(int l=1;l<=n;l++){
        int r=l;
        for(int i=0;i<20;i++){
            if(((1<<i)&s))r=nxt[r][i];
        }
        //cout<<l<<' '<<r<<endl;
        mx=max(mx,{pre[r-1]-pre[l-1],l});
    }
    vector<int>ans;
    int l=mx.second;
    while(l<=n&&s){
        ans.pb(sh[l]);
        l=nxt[l][0];
        s--;
    }

    cout<<ans.size()<<endl;
    for(auto x:ans)cout<<x<<' ';cout<<endl;
    return 0;
}
*/

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;
const ll inf=1e9+10;
const ll maxn=6050;
ll n,m,k,a,b;
ll s[maxn],val[maxn],t[maxn];
ll dp[maxn][maxn][2][2];
bool vis[maxn][maxn][2][2];
ll solve(ll day,ll sc,ll f1,ll f2){
    if(vis[day][sc][f1][f2])return dp[day][sc][f1][f2];
    vis[day][sc][f1][f2]=1;
    ll &ans=dp[day][sc][f1][f2];
    ans=-1e9;
    if(sc==m)return ans=0;
    if(day==n)return ans=solve(day,sc+1,f1,0)-b-a*f2;
    ans=max(ans,solve(day,sc+1,f1,0)-b-a*f2);
    ans=max(ans,solve(day+1,sc,0,f2)-b-a*f1);
    if(s[day]==t[sc])ans=max(ans,val[s[day]]+solve(day+1,sc+1,1,1));
    return ans;
}
int main()
{
    IOS
    cin>>k>>n>>m>>a>>b;
    for(ll i=1;i<=k;i++)cin>>val[i];
    for(ll i=0;i<n;i++)cin>>s[i];
    for(ll i=0;i<m;i++)cin>>t[i];
    a=-a;
    b=-b;

    for(ll i=0;i<n+10;i++){
        for(ll j=0;j<m+10;j++){
            for(ll k=0;k<2;k++){
                for(ll l=0;l<2;l++){
                    dp[i][j][k][l]=-1e9;
                }
            }
        }
    }

    for(ll day=0;day<n+10;day++){
        for(ll f1=0;f1<2;f1++){
            for(ll f2=0;f2<2;f2++){
                dp[day][m][f1][f2]=0;
            }
        }
    }

    for(ll sc=m-1;sc>=0;sc--){
        for(ll day=n;day>=0;day--){
            for(ll f1=0;f1<2;f1++){
                for(ll f2=0;f2<2;f2++){
                    ll &ans=dp[day][sc][f1][f2];
                    if(day==n){ans=dp[day][sc+1][f1][0]-b-a*f2;continue;}
                    ans=max(ans,dp[day][sc+1][f1][0]-b-a*f2);
                    ans=max(ans,dp[day+1][sc][0][f2]-b-a*f1);
                    if(s[day]==t[sc])ans=max(ans,dp[day+1][sc+1][1][1]+val[s[day]]);
                }
            }
        }
    }
    ll ans=-a-b*m;
    for(ll i=0;i<=n;i++){
        ans=max(ans,dp[i][0][1][1]);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 52 ms 31616 KB Output is correct
3 Correct 5 ms 2048 KB Output is correct
4 Correct 7 ms 4736 KB Output is correct
5 Correct 5 ms 2304 KB Output is correct
6 Correct 17 ms 11392 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 8 ms 4736 KB Output is correct
9 Correct 29 ms 18944 KB Output is correct
10 Correct 62 ms 36608 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 14 ms 9216 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 7 ms 3456 KB Output is correct
6 Correct 23 ms 18176 KB Output is correct
7 Correct 23 ms 17920 KB Output is correct
8 Correct 39 ms 25984 KB Output is correct
9 Correct 8 ms 3840 KB Output is correct
10 Correct 63 ms 36480 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 88448 KB Output is correct
2 Correct 58 ms 42368 KB Output is correct
3 Runtime error 124 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 88448 KB Output is correct
2 Correct 58 ms 42368 KB Output is correct
3 Runtime error 124 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 88448 KB Output is correct
2 Correct 58 ms 42368 KB Output is correct
3 Runtime error 124 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 5 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 5 ms 1152 KB Output is correct
15 Correct 5 ms 1152 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 52 ms 31616 KB Output is correct
3 Correct 5 ms 2048 KB Output is correct
4 Correct 7 ms 4736 KB Output is correct
5 Correct 5 ms 2304 KB Output is correct
6 Correct 17 ms 11392 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 8 ms 4736 KB Output is correct
9 Correct 29 ms 18944 KB Output is correct
10 Correct 62 ms 36608 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 14 ms 9216 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 7 ms 3456 KB Output is correct
16 Correct 23 ms 18176 KB Output is correct
17 Correct 23 ms 17920 KB Output is correct
18 Correct 39 ms 25984 KB Output is correct
19 Correct 8 ms 3840 KB Output is correct
20 Correct 63 ms 36480 KB Output is correct
21 Correct 139 ms 88448 KB Output is correct
22 Correct 58 ms 42368 KB Output is correct
23 Runtime error 124 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -