Submission #110821

#	Time	Username	Problem	Language	Result	Execution time	Memory
110821		ayaze	Money (IZhO17_money)	C++14	0 / 100	2 ms	384 KiB

money

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

map<int, int> m;

vector<int> v;
vector<vector<int>> positions;
int n;

int dp[N];

void init() {
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++) {
        int x; scanf("%d", &x);
        
        if (v.empty() || v.back() != x) {
            v.push_back(x);
        }       
    }
    n = v.size();
}

void prepare() {
    set<int> s;
    for (int x : v) s.insert(x);
    
    int cnt = 0;
    for (int x : s) {
        m[x] = cnt;
        cnt++;
    }
    
    positions.resize(cnt);
    
    for (int i = 0 ; i < v.size() ; i++) {
        v[i] = m[v[i]];
        positions[v[i]].push_back(i);
    }
}

int DP() {
    pair<int, int> best = {-1, -1};
    pair<int, int> best2 = {-1, -1};
    
    for (int i = 0 ; i < positions[positions.size()-1].size() ; i++) {
        int idx = positions[positions.size()-1][i];
        
        if (best2.first < 0) best2 = {0, idx};
        if (best.first < best2.first) swap(best, best2);
    }
    
    for (int i = (int)positions.size()-2 ; i >= 0 ; i--) {
        for (int idx : positions[i]) {
            dp[idx] = best.first;
            
            // continue
            if (idx+1 < n && v[idx+1] == v[idx]+1) {
                // only segment
                if (best2.first == -1) {
                    dp[idx] = max(dp[idx], 1 + dp[idx+1]);
                } else {
                    int val = best.first;
                    if (best.second == idx+1)
                        val = best2.first;
                    dp[idx] = max(dp[idx], 1 + val);
                }
            }
        }
        
        best = {-1, -1};
        best2 = {-1, -1};
        for (int idx : positions[i]) {
            if (best2.first < dp[idx]) best2 = {dp[idx], idx};
            if (best.first < best2.first) swap(best, best2);
        }
    }
    
    int ret = 0;
    for (int x : positions[0]) {
        ret = max(ret, dp[x]);
    }
    
    return ret;
}

int work() {
    int ret = n-1;
    ret -= DP();
    
    return ret;
}

int main() {
    init();
    prepare();
    printf("%d\n", work());
    return 0;
}

Compilation message (stderr)

money.cpp: In function 'void prepare()':
money.cpp:38:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < v.size() ; i++) {
                      ~~^~~~~~~~~~
money.cpp: In function 'int DP()':
money.cpp:48:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < positions[positions.size()-1].size() ; i++) {
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
money.cpp: In function 'void init()':
money.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
money.cpp:17:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55