Submission #589286

#	Time	Username	Problem	Language	Result	Execution time	Memory
589286		MohamedFaresNebili	Art Exhibition (JOI18_art)	C++14	100 / 100	216 ms	48416 KiB

art

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
                #define int ll
                #define double ld

                const int MOD = 1000 * 1000 * 1000 + 7;
                const double EPS = 1e-9;

                int N, P[500001], DP[500001];
                pair<int, int> A[500001];
                int solve(int i) {
                    if(i == N + 1)
                        return -A[N].ff;
                    if(DP[i] != -1) return DP[i];
                    int best = A[i].ss + max(solve(i + 1), -A[i].ff);
                    return DP[i] = best;
                }

                int32_t main() {
                    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                    cin >> N; memset(DP, -1, sizeof DP);
                    for(int l = 1; l <= N; l++)
                        cin >> A[l].ff >> A[l].ss;
                    sort(A + 1, A + N + 1);
                    int res = 0;
                    for(int l = 1; l <= N; l++)
                        res = max(res, A[l].ff + solve(l));
                    cout << res << "\n";
                    return 0;
                }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50