Submission #210586

#TimeUsernameProblemLanguageResultExecution timeMemory
210586mayhoubsalehVisiting Singapore (NOI20_visitingsingapore)C++14
0 / 100
222 ms45688 KiB
#include <bits/stdc++.h> #include <string> #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 maxn=5050; int n,k,m,a,b; int s[maxn],t[maxn],val[maxn]; int dp[maxn][maxn][2]; bool vis[maxn][maxn][2]; int solve(int i,int j,int took,int happy=0){ //cout<<i<<' '<<j<<' '<<took<<' '<<happy<<endl; if(vis[i][j][took])return dp[i][j][took]; vis[i][j][took]=1; int &ans=dp[i][j][took]; if(i==n&&j==m)return ans=happy; if(i==n)return ans=solve(i,j+1,0,happy+b+(a*took)); if(j==m)return ans=solve(i+1,j,took,happy); ans=solve(i,j+1,0,happy+b+(a*took)); //return ans; if(s[i]==t[j]){ ans=max(ans,solve(i+1,j+1,1,happy+val[s[i]])); } ans=max(ans,solve(i+1,j,took,happy)); return ans; } void path(int i,int j,int took){ cout<<i<<' '<<j<<' '<<took<<endl; if(i==n||j==m)return; int ans=dp[i][j][took]; if(ans=b+(a*took)+solve(i,j+1,0)){ path(i,j+1,0); return; } if(s[i]==t[j]&&ans==solve(i+1,j+1,1)+val[s[i]]){ cout<<j<<' '; path(i+1,j+1,1); return; } if(ans==solve(i+1,j,took))path(i+1,j,took); } int main() { IOS cin>>k>>n>>m>>a>>b; //cout<<a<<' '<<b<<endl; 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]; //for(int i=1;i<=k;i++)cout<<val[i]<<' ';cout<<endl; //for(int i=0;i<n;i++)cout<<s[i]<<' ';cout<<endl; //for(int i=0;i<m;i++)cout<<t[i]<<' ';cout<<endl; cout<<solve(0,0,1)<<endl; //path(0,0,1); //cout<<endl; return 0; }

Compilation message (stderr)

VisitingSingapore.cpp: In function 'void path(int, int, int)':
VisitingSingapore.cpp:36:11: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
     if(ans=b+(a*took)+solve(i,j+1,0)){
        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...