oj.uz

Submission #846909

# Submission time Handle Problem Language Result Execution time Memory
846909 2023-09-08T16:06:32 Z Abito Financial Report (JOI21_financial) C++17
17 / 100
 486 ms 23188 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=3e5+5,M=405;
int a[N],n,d,bit[N],seg[4*N+5],b[N],dp[M][M][M];
bool vis[M][M][M];
void upd(int x){
    while (x<=n){
        bit[x]++;
        x+=x&-x;
    }return;
}int calc(int x){
    int y=0;
    while (x){
        y+=bit[x];
        x-=x&-x;
    }return y;
}
int rec(int i,int last,int mx){
    if (i-last>d && last) return INT_MIN;
    if (i>n && last!=n) return INT_MIN;
    if (i>n) return 0;
    if (vis[i][last][mx]) return dp[i][last][mx];
    vis[i][last][mx]=true;
    int nextmx=mx;
    if (a[i]>a[mx]) nextmx=i;
    return dp[i][last][mx]=max(rec(i+1,last,mx),rec(i+1,i,nextmx)+bool(nextmx==i));
}
int edit(int node,int l,int r,int idx,int val){
    if (l==r) return seg[node]=val;
    int mid=(l+r)/2;
    if (idx<=mid) return seg[node]=max(edit(node*2,l,mid,idx,val),seg[node*2+1]);
    return seg[node]=max(edit(node*2+1,mid+1,r,idx,val),seg[node*2]);
}
int query(int node,int l,int r,int lx,int rx){
    if (r<lx || l>rx) return 0;
    if (l>=lx && r<=rx) return seg[node];
    int mid=(l+r)/2;
    return max(query(node*2,l,mid,lx,rx),query(node*2+1,mid+1,r,lx,rx));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>d;
    for (int i=1;i<=n;i++) cin>>a[i];
    a[0]=INT_MIN;
    if (d==1){
        stack<int> s;
        for (int i=1;i<=n;i++){
            while (!s.empty()){
                if (a[s.top()]<a[i]) s.pop();
                else{
                    b[i]=s.top();
                    break;
                }
            }s.push(i);
        }
        int ans=0;
        for (int i=n;i;i--){
            upd(b[i]+1);
            ans=max(ans,calc(i));
        }cout<<ans<<endl;
        return 0;
    }
    if (d){
        map<int,int> mp;mp[INT_MIN]++;
        for (int i=1;i<=n;i++) mp[a[i]]++;
        int c=0;
        for (auto u:mp) mp[u.F]=c++;
        for (int i=1;i<=n;i++){
            a[i]=mp[a[i]];
            edit(1,1,n,a[i],query(1,1,n,0,a[i]-1)+1);
        }cout<<query(1,1,n,0,4*N+4)<<endl;
        return 0;
    }cout<<rec(1,0,0)<<endl;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Incorrect 1 ms 4440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Incorrect 1 ms 4440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Incorrect 1 ms 4440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6232 KB Output is correct
2 Correct 33 ms 5336 KB Output is correct
3 Correct 35 ms 5332 KB Output is correct
4 Correct 33 ms 4956 KB Output is correct
5 Correct 33 ms 5056 KB Output is correct
6 Correct 36 ms 5164 KB Output is correct
7 Correct 47 ms 3028 KB Output is correct
8 Correct 33 ms 6236 KB Output is correct
9 Correct 42 ms 5160 KB Output is correct
10 Correct 34 ms 5580 KB Output is correct
11 Correct 34 ms 4956 KB Output is correct
12 Correct 34 ms 4952 KB Output is correct
13 Correct 35 ms 4948 KB Output is correct
14 Correct 35 ms 5160 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7124 KB Output is correct
2 Correct 93 ms 4952 KB Output is correct
3 Correct 154 ms 5388 KB Output is correct
4 Correct 486 ms 21580 KB Output is correct
5 Correct 397 ms 21640 KB Output is correct
6 Correct 436 ms 21572 KB Output is correct
7 Correct 197 ms 23188 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 200 ms 22864 KB Output is correct
10 Correct 258 ms 21260 KB Output is correct
11 Correct 396 ms 21432 KB Output is correct
12 Correct 363 ms 21572 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Incorrect 1 ms 4440 KB Output isn't correct
15 Halted 0 ms 0 KB -