Submission #123161

#	Time	Username	Problem	Language	Result	Execution time	Memory
123161		Hideo	Art Exhibition (JOI18_art)	C++14	100 / 100	603 ms	150136 KiB

art

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

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pl pair < ll, ll >
#define pii pair < int, pi >
#define vii vector < pi >

const int N = 5e5 + 7;
const int INF = 1e9 + 7;

pl a[N];
ll st[N][32], pr[N];
ll ans;
int n;

void build (){
    for (int i = 1; i <= 30; i++){
        for (int j = 1; j + (1 << i) - 1 <= n; j++){
            st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }
}

ll get (int l, int r){
    int pw = log2(r - l + 1);
    return max(st[l][pw], st[r - (1 << pw) + 1][pw]);
}

main(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].fr, &a[i].sc);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        pr[i] = pr[i - 1] + a[i].sc;

    for (int i = 1; i <= n; i++)
        st[i][0] = pr[i] - a[i].fr;

    build();
    for (int i = 1; i <= n; i++){
        ans = max(ans, a[i].fr - pr[i - 1] + get(i, n));
    }
    cout << ans;
}

Compilation message (stderr)

art.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
art.cpp: In function 'int main()':
art.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &a[i].fr, &a[i].sc);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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