oj.uz

Submission #211215

# Submission time Handle Problem Language Result Execution time Memory
211215 2020-03-19T13:02:59 Z mayhoubsaleh Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 729 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;

    ll ans=-a-b*m;
    for(ll i=0;i<=n;i++){
        ans=max(ans,solve(i,0,1,1));
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 91 ms 38264 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 30 ms 15104 KB Output is correct
7 Correct 6 ms 2304 KB Output is correct
8 Correct 12 ms 6656 KB Output is correct
9 Correct 56 ms 23672 KB Output is correct
10 Correct 110 ms 44160 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 23 ms 11136 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 10 ms 4224 KB Output is correct
6 Correct 49 ms 22268 KB Output is correct
7 Correct 48 ms 21496 KB Output is correct
8 Correct 81 ms 31748 KB Output is correct
9 Correct 11 ms 4864 KB Output is correct
10 Correct 125 ms 44156 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 107772 KB Output is correct
2 Correct 117 ms 55672 KB Output is correct
3 Runtime error 729 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 245 ms 107772 KB Output is correct
2 Correct 117 ms 55672 KB Output is correct
3 Runtime error 729 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 245 ms 107772 KB Output is correct
2 Correct 117 ms 55672 KB Output is correct
3 Runtime error 729 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 1024 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 5 ms 1536 KB Output is correct
11 Correct 5 ms 1536 KB Output is correct
12 Correct 7 ms 1536 KB Output is correct
13 Correct 6 ms 1536 KB Output is correct
14 Correct 5 ms 1536 KB Output is correct
15 Correct 6 ms 1536 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 91 ms 38264 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 30 ms 15104 KB Output is correct
7 Correct 6 ms 2304 KB Output is correct
8 Correct 12 ms 6656 KB Output is correct
9 Correct 56 ms 23672 KB Output is correct
10 Correct 110 ms 44160 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 23 ms 11136 KB Output is correct
14 Correct 6 ms 1408 KB Output is correct
15 Correct 10 ms 4224 KB Output is correct
16 Correct 49 ms 22268 KB Output is correct
17 Correct 48 ms 21496 KB Output is correct
18 Correct 81 ms 31748 KB Output is correct
19 Correct 11 ms 4864 KB Output is correct
20 Correct 125 ms 44156 KB Output is correct
21 Correct 245 ms 107772 KB Output is correct
22 Correct 117 ms 55672 KB Output is correct
23 Runtime error 729 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -