제출 #1182016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182016		nekolie	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	101 ms	12544 KiB

Main

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    pair<int,int> risa[n];
    vector<pair<int,int>> zabijmnie;
    for (int i = 0; i < n; i++)
        cin >> risa[i].first >> risa[i].second;
    if (n == 1)
        cout << 1 << endl;
    else {
        int dp[n][2], odp = 0;
        sort(risa,risa+n);
        for (int i = 0; i < n; i++)
            if (i == 0 || risa[i] != zabijmnie.back())
                zabijmnie.push_back(risa[i]);
        int m = zabijmnie.size();
        for (int i = 0; i < m; i++)
            risa[i] = zabijmnie[i];
        if (m == 1)
            cout << 1 << endl;
        else {
            dp[0][0] = risa[0].first+risa[0].second, dp[m-1][1] = risa[m-1].second-risa[m-1].first;
            for (int i = 1; i < m; i++)
                dp[i][0] = max(dp[i-1][0],risa[i].first+risa[i].second);
            for (int i = m-2; i >= 0; i--)
                dp[i][1] = max(dp[i+1][1],risa[i].second-risa[i].first);
            if (risa[0].second-risa[0].first > dp[1][1])
                odp++;
            if (risa[m-1].first+risa[m-1].second > dp[m-2][0])
                odp++;
            for (int i = 1; i < m-1; i++)
                if (risa[i].second-risa[i].first > dp[i+1][1] && risa[i].first+risa[i].second > dp[i-1][0])
                    odp++;
            cout << odp << endl;
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31