oj.uz

Submission #173287

# Submission time Handle Problem Language Result Execution time Memory
173287 2020-01-03T17:46:30 Z DeD_TihoN Money (IZhO17_money) C++14
0 / 100
 25 ms 24184 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=1000+7;
const int inf=1e18+1e9;
const int mod=1e9+7;
const ld eps=1e-9;

int a[N];
int dp[N][N];
bool used[N][N];
vector< vector<int> >b[N][N];

int get_dp(int l,int r)
{
    if (l>r){
        return 0;
    }
    if (used[l][r]){
        return dp[l][r];
    }
    used[l][r]=true;
    dp[l][r]=inf;
    if (l==r){
        dp[l][r]=1;
    }
    else {
        for (int j=l;j<r;++j){
            dp[l][r]=min(dp[l][r],get_dp(l,j)+get_dp(j+1,r));
        }
        for (int j=0;j<b[l][r].size();++j){
            vector<int>d=b[l][r][j];
            int res=0;
            int last=l-1;
            for (int k=0;k<d.size();++k){
                res+=get_dp(last+1,d[k]-1);
                last=d[k];
            }
            res+=get_dp(last+1,r);
            dp[l][r]=min(dp[l][r],res+1);
        }
    }
    return dp[l][r];
}

main ()
{
    ios;
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    for (int i=1;i<=n;++i){
        int r=i+1;
        vector<int>c;
        c.pb(a[i]);
        while(r<=n && a[r]>a[r-1]){
            c.pb(a[r]);
            b[a[i]][a[r]].pb(c);
            ++r;
        }
        i=r-1;
    }
    cout<<get_dp(1,n)<<endl;
}

Compilation message

money.cpp: In function 'long long int get_dp(long long int, long long int)':
money.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<b[l][r].size();++j){
                      ~^~~~~~~~~~~~~~~
money.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k=0;k<d.size();++k){
                          ~^~~~~~~~~
money.cpp: At global scope:
money.cpp:75:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 25 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Incorrect 25 ms 24184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 25 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Incorrect 25 ms 24184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 25 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Incorrect 25 ms 24184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24184 KB Output is correct
2 Correct 25 ms 24184 KB Output is correct
3 Correct 25 ms 24184 KB Output is correct
4 Incorrect 25 ms 24184 KB Output isn't correct
5 Halted 0 ms 0 KB -