oj.uz

Submission #546235

# Submission time Handle Problem Language Result Execution time Memory
546235 2022-04-06T18:20:12 Z LunaMeme Art Exhibition (JOI18_art) C++14
0 / 100
 0 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -