Submission #1055344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055344		YassirSalama	Financial Report (JOI21_financial)	C++17	48 / 100	2671 ms	404048 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
const int maxn=7000+100;
#define all(v) v.begin(),v.end()
template<typename T> 
void dbg(const T& t){
    cout<<t<<endl;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
    cout<<t<<" , ";
    dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : ";dbg(__VA_ARGS__);

int dp[maxn][maxn];
int n,d;
map<int,int> mp;
vector<int> v;
int ANS=0;
int solve(int i,int j,int D){
    if(D==0) return -1e18;
    if(i==n) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    int &ans=dp[i][j];ans=0;
    int t=mp[v[i]];
    if(t>j){
        ans=max(ans,solve(i+1,t,d)+1);
    }else{
        ans=max(ans,solve(i+1,j,d));
    }
    ans=max(ans,solve(i+1,j,D-1));
    ANS=max(ANS,solve(i+1,t,d)+1);
    return ans;
}
signed main(){
    memset(dp,-1,sizeof(dp));
    cin>>n>>d;
    v.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> c=v;c.insert(c.begin(),-1);sort(all(c));c.erase(unique(all(c)),c.end());
    for(int i=0;i<c.size();i++) mp[c[i]]=i;
    int x=solve(0,0,d);
    cout<<max(ANS,x)<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<c.size();i++) mp[c[i]]=i;
      |                 ~^~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35