Submission #840565

#	Time	Username	Problem	Language	Result	Execution time	Memory
840565		overwatch9	Art Exhibition (JOI18_art)	C++17	100 / 100	807 ms	48244 KiB

art

// slightly modified kadane's algorithm
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
vector <pair <ll, ll>> pnts;
int main() {
    int n;
    cin >> n;
    map <ll, ll> mp;
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        mp[a] += b;
    }
    ll ans = 0;
    ll mn = mp.begin()->first;
    ll mx = mn;
    vector <ll> dp(mp.size());
    int i = 0;
    ll tot_val = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        mx = it->first;
        tot_val += it->second;
        ll tp_ans = tot_val - (mx - mn);
        if (tp_ans <= it->second) {
            mn = mx = it->first;
            tp_ans = tot_val = it->second;
        }
        dp[i++] = tp_ans;
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:18:8: warning: unused variable 'ans' [-Wunused-variable]
   18 |     ll ans = 0;
      |        ^~~

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