JOI2018/2019 予選参加記

結果

ABCDEfの5完506点 DEがやけに簡単だと思いました

始まる前

りゅうおうのおしごと！を見ていた これ泣いちゃうんですよね

問題

全部GitHubにあります

github.com

D

まあソートしてはいなんですけど、全部0に気づかなくていろいろ実装を直したので汚い

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    i64 n;
    cin >> n;
    vector<i64> a(n);
    for(i64 i = 0; i < n; ++i){
        cin >> a[i];
        if(i != 0 && a[i] == a[i - 1]){
            i--; n--;
        }
    }
    if(n == 1 && a[0] == 0){
        cout << 0 << endl;
        return 0;
    }
    vector<P> sorted;
    for(i64 i = 0; i < n; ++i){
        sorted.push_back(P(a[i], i + 2));
    }
    sort(sorted.begin(), sorted.end(), greater<P>());
    unordered_map<i64, vector<P>> mp;
    i64 cnt = 0;
    for(i64 i = 0; i < n; ++i){
        if(i == 0){
            mp[cnt].push_back(sorted[i]);
        }else{
            if(sorted[i].first == sorted[i - 1].first){
                mp[cnt].push_back(sorted[i]);
            }else{
                cnt++;
                mp[cnt].push_back(sorted[i]);
            }
        }
        if(i == n - 1 && mp[cnt][0].first != 0){
            cnt++;
            mp[cnt] = {P(0, 1), P(0, n + 2)};
        }
    }
    vector<bool> used(n + 10, false);
    i64 tmp, ans;
    tmp = ans = 0;
    for(i64 i = 0; i < cnt + 1; ++i){
        for(i64 j = 0; j < mp[i].size(); ++j){
            i64 num = mp[i][j].second;
            if(used[num - 1] && used[num + 1]) tmp--;
            else if(!used[num - 1] && !used[num + 1]) tmp++;
            used[num] = true;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

E

DPパートが簡単だったのですんなりいった ソートをしましょう

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    i64 n, m;
    cin >> n >> m;
    vector<i64> a(n + 10), l(m), r(m);
    vector<P> sorted(m);
    for(i64 i = 0; i < n; ++i) cin >> a[i + 1];
    for(i64 i = 0; i < m; ++i){
        cin >> l[i] >> r[i];
        sorted[i] = P(l[i], r[i]);
    }
    sort(sorted.begin(), sorted.end());
    vector<i64> min_index(n + 10, -1);
    i64 cnt = 0;
    for(i64 i = 0; i < m; ++i){
        cnt = max(cnt, sorted[i].first);
        while(sorted[i].second >= cnt){
            min_index[cnt] = sorted[i].first;
            cnt++;
        }
    }
    vector<i64> dp(n + 10, 0);
    for(i64 i = 1; i < n + 1; ++i){
        if(min_index[i] == -1){
            dp[i] = dp[i - 1] + a[i];
        }else{
            dp[i] = max(dp[i - 1], dp[min_index[i] - 1] + a[i]);
        }
    }
    //for(i64 i = 1; i < n + 1; ++i) cout << i << ": " << min_index[i] << endl;
    cout << dp[n] << endl;
}

感想

今年も本選に行けそうなので嬉しい 真面目に精進して春合宿行くぞい