oj.uz

Submission #211213

# Submission time Handle Problem Language Result Execution time Memory
211213 2020-03-19T13:00:56 Z mayhoubsaleh Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 1064 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 int inf=1e9+10;
const int maxn=5e3+100;
int n,m,k,a,b;
int s[maxn],val[maxn],t[maxn];
int dp[maxn][maxn][2][2];
bool vis[maxn][maxn][2][2];
int solve(int day,int sc,int f1,int f2){
    if(vis[day][sc][f1][f2])return dp[day][sc][f1][f2];
    vis[day][sc][f1][f2]=1;
    int &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(int i=1;i<=k;i++)cin>>val[i];
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<m;i++)cin>>t[i];
    a=-a;
    b=-b;

    int ans=-a-b*m;
    for(int 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 2432 KB Output is correct
2 Correct 88 ms 24824 KB Output is correct
3 Correct 7 ms 2560 KB Output is correct
4 Correct 12 ms 7808 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 28 ms 11264 KB Output is correct
7 Correct 6 ms 2048 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 55 ms 16120 KB Output is correct
10 Correct 112 ms 28392 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 25 ms 7424 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 10 ms 3072 KB Output is correct
6 Correct 52 ms 14712 KB Output is correct
7 Correct 45 ms 13944 KB Output is correct
8 Correct 68 ms 20600 KB Output is correct
9 Correct 10 ms 3712 KB Output is correct
10 Correct 107 ms 28212 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 69472 KB Output is correct
2 Correct 108 ms 40056 KB Output is correct
3 Correct 817 ms 192248 KB Output is correct
4 Runtime error 1064 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 69472 KB Output is correct
2 Correct 108 ms 40056 KB Output is correct
3 Correct 817 ms 192248 KB Output is correct
4 Runtime error 1064 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 69472 KB Output is correct
2 Correct 108 ms 40056 KB Output is correct
3 Correct 817 ms 192248 KB Output is correct
4 Runtime error 1064 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 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 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 6 ms 1408 KB Output is correct
11 Correct 6 ms 1408 KB Output is correct
12 Correct 6 ms 1408 KB Output is correct
13 Correct 5 ms 1408 KB Output is correct
14 Correct 6 ms 1408 KB Output is correct
15 Correct 6 ms 1408 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2432 KB Output is correct
2 Correct 88 ms 24824 KB Output is correct
3 Correct 7 ms 2560 KB Output is correct
4 Correct 12 ms 7808 KB Output is correct
5 Correct 6 ms 3456 KB Output is correct
6 Correct 28 ms 11264 KB Output is correct
7 Correct 6 ms 2048 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 55 ms 16120 KB Output is correct
10 Correct 112 ms 28392 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 25 ms 7424 KB Output is correct
14 Correct 6 ms 1152 KB Output is correct
15 Correct 10 ms 3072 KB Output is correct
16 Correct 52 ms 14712 KB Output is correct
17 Correct 45 ms 13944 KB Output is correct
18 Correct 68 ms 20600 KB Output is correct
19 Correct 10 ms 3712 KB Output is correct
20 Correct 107 ms 28212 KB Output is correct
21 Correct 236 ms 69472 KB Output is correct
22 Correct 108 ms 40056 KB Output is correct
23 Correct 817 ms 192248 KB Output is correct
24 Runtime error 1064 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -