[JOI精進録] 難易度7「イルミネーション」(JOI2018/2019 予選E)

JOIにイルミネーションなんか2つある

問題リンク

atcoder.jp

問題概要

イルミネーションをいくつかつける。美しさの総和の最大値を求めなさい。
ただし指定されている個指定されている区間内には各1つまでしか飾り付けることができない。

解説

AC解法 (100/100点)

イルミネーションをまで飾り付ける、つけないを決めたときの美しさの総和
として、更新していく。区間はmultisetで管理して、最小値から取得する場所を決定する。

ACコード

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

int main(){
#define int long long
  int n,m; cin >> n >> m;
  vector<int> A(n),dp(n+1); for (int &a:A) cin >> a;
  vector<pair<int,int>> Add(m); multiset<pair<int,int>> Sub; multiset<int> Notwo;
  for (auto& [a,b]:Add) (cin >> a >> b),Sub.emplace(b,a);
  sort(Add.begin(), Add.end());
  int k(0);
  for (int i(0);i < n;++i){
    while(k<m&&Add[k].first<i+2) Notwo.emplace(Add[k].first),++k;
    dp[i+1] = max(dp[max((*Notwo.begin())-1,0ll)]+A[i],dp[i]+(Notwo.empty()?A[i]:0));
    while(!Sub.empty()&&Sub.begin()->first<i+2) Notwo.erase(Notwo.find(Sub.begin()->second)),Sub.erase(Sub.begin());
  }
  cout << dp[n] << endl;
}

提出結果

atcoder.jp