Submission #546235

#	Time	Username	Problem	Language	Result	Execution time	Memory
546235		LunaMeme	Art Exhibition (JOI18_art)	C++14	0 / 100	0 ms	212 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)

struct p{
    ll size, val;
    bool operator<(p rhs){
        return size < rhs.size; 
    }
};

int main(){
    int n; cin >> n;
    vector<p> v(n);
    FOR(i, 0, n){
        ll a, b; cin >>  a >> b;
        p obj;
        obj.size = a;
        obj.val = b;
        v[i] = obj;
    }
    sort(v.begin(), v.end());

    //left to right
    ll best_r = 0;
    int indx = 0;
    ll best_sum = 0, curr_sum = 0;
    FOR(i, 0, n){
        if (curr_sum + v[i].val >=  v[i].size - best_r){
            best_r = v[i].size;
            indx = i;
            best_sum += (curr_sum + v[i].val);
            curr_sum = 0;
        }
        else{
            curr_sum += v[i].val;
        }
    }
    //cout << best_r << ' ' << best_sum << '\n';

    //right to left
    int best_l = indx;
    curr_sum = 0;
    best_sum = 0;
    for(int i = indx; i >= 0; i --){
        if (curr_sum + v[i].val >=  best_l - v[i].size){
            best_l = v[i].size;
            indx = i;
            best_sum += curr_sum + v[i].val;
            curr_sum = 0;
        }
        else{
            curr_sum += v[i].val;
        }
    }
    cout << best_sum - (best_r - best_l) << '\n';

}

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