Submission #810957

#	Time	Username	Problem	Language	Result	Execution time	Memory
810957		nemethm	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	212 KiB

art

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

const ll mod = 1e9 + 7;
vector<ll> pf;

vector<pair<ll, ll>> temp;

ll sum(int l, int r){
    if(l == 0) return pf[r];
    return pf[r] - pf[l - 1];
}
 
ll eval(int l, int r){
    if(l > r) return -1;
    return sum(l, r)- (temp[r].first - temp[l].first);
}

int main(){
    int n;
    cin >> n;
    temp.resize(n);
    for(auto& i : temp){
        cin >> i.first >> i.second;
    }
    sort(begin(temp), end(temp));
    pf.resize(n);
    pf[0] = temp[0].second;
    for(int i = 1; i < n; ++i){
        pf[i] = pf[i - 1] + temp[i].second;
    }
    int i = 0;
    vector<pair<ll, ll>> v;
    while(i < n){
        ll s = temp[i].second;
        int start = i;
        while(i + 1 < n && temp[i].first - temp[i + 1].first + temp[i + 1].second > 0){
            ++i;
        }
        v.push_back({start, i});
        ++i;
    }
    ll sol = 0;
    i = 0;
    while(i < v.size()){
        int start = i;
        while(i + 1 < v.size() && eval(v[start].first, v[i + 1].second) > eval(v[i + 1].first, v[i + 1].second) && eval(v[start].first, v[i + 1].second) >= eval(v[start].first, v[i].second)){
            //cerr << "adsd" << endl;
            ++i;
        }
        //cerr << "ad " << start << " " << i << endl; 
        sol = max(sol, eval(v[start].first, v[i].second));
        ++i;
    }
    cout << sol << endl;
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:37:12: warning: unused variable 's' [-Wunused-variable]
   37 |         ll s = temp[i].second;
      |            ^
art.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while(i < v.size()){
      |           ~~^~~~~~~~~~
art.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(i + 1 < v.size() && eval(v[start].first, v[i + 1].second) > eval(v[i + 1].first, v[i + 1].second) && eval(v[start].first, v[i + 1].second) >= eval(v[start].first, v[i].second)){
      |               ~~~~~~^~~~~~~~~~

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