oj.uz

Submission #1115390

# Submission time Handle Problem Language Result Execution time Memory
1115390 2024-11-20T12:13:13 Z staszic_ojuz Art Exhibition (JOI18_art) C++17
50 / 100
 131 ms 17584 KB 
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const int MAX=5*1e3+7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    ll a, b, cale=0, mmin=1e16, mmax=0;
    vector<pair<ll, ll>> prace;

    for (int i=0; i<n; i++){
        cin >> a >> b;
        cale += b;
        mmin = min(mmin, a);
        mmax = max(mmax, a);
        prace.push_back({a, b});
    }
    
    cale -= (mmax-mmin);

    sort(prace.begin(), prace.end());

    pair<ll, ll> pref[MAX];
    pair<ll, ll> suf[MAX];
    
    pref[0] = {0, 0};

    for (int i=1; i<n; i++){
        pref[i].first = pref[i-1].first - prace[i-1].second+(prace[i].first-prace[i-1].first);
        pref[i].second = max(pref[i].first, pref[i-1].second);
    }

    suf[n] = {0, 0};

    for (int i=n-2; i>0; i--){
        suf[i].first = suf[i+1].first - prace[i+1].second+(prace[i+1].first-prace[i].first);
        suf[i].second = max(suf[i].first, suf[i+1].second);
    }

    ll wyn=0;

    for (int i=0; i<=n; i++){
        wyn = max(wyn, pref[i].second+suf[i].second);
    }

    cout << cale+wyn << "\n";
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 760 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 760 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 1 ms 592 KB Output is correct
22 Correct 1 ms 592 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 760 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 760 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 1 ms 592 KB Output is correct
22 Correct 1 ms 592 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 3 ms 592 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 2 ms 592 KB Output is correct
32 Correct 2 ms 592 KB Output is correct
33 Correct 2 ms 592 KB Output is correct
34 Correct 2 ms 592 KB Output is correct
35 Correct 4 ms 592 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 2 ms 780 KB Output is correct
38 Correct 2 ms 592 KB Output is correct
39 Correct 2 ms 592 KB Output is correct
40 Correct 2 ms 592 KB Output is correct
41 Correct 2 ms 592 KB Output is correct
42 Correct 2 ms 724 KB Output is correct
43 Correct 3 ms 592 KB Output is correct
44 Correct 2 ms 592 KB Output is correct
45 Correct 2 ms 592 KB Output is correct
46 Correct 2 ms 592 KB Output is correct
47 Correct 3 ms 592 KB Output is correct
48 Correct 2 ms 592 KB Output is correct
49 Correct 2 ms 592 KB Output is correct
50 Correct 2 ms 592 KB Output is correct
51 Correct 2 ms 592 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 760 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 1 ms 760 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 1 ms 592 KB Output is correct
22 Correct 1 ms 592 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 3 ms 592 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 2 ms 592 KB Output is correct
31 Correct 2 ms 592 KB Output is correct
32 Correct 2 ms 592 KB Output is correct
33 Correct 2 ms 592 KB Output is correct
34 Correct 2 ms 592 KB Output is correct
35 Correct 4 ms 592 KB Output is correct
36 Correct 2 ms 592 KB Output is correct
37 Correct 2 ms 780 KB Output is correct
38 Correct 2 ms 592 KB Output is correct
39 Correct 2 ms 592 KB Output is correct
40 Correct 2 ms 592 KB Output is correct
41 Correct 2 ms 592 KB Output is correct
42 Correct 2 ms 724 KB Output is correct
43 Correct 3 ms 592 KB Output is correct
44 Correct 2 ms 592 KB Output is correct
45 Correct 2 ms 592 KB Output is correct
46 Correct 2 ms 592 KB Output is correct
47 Correct 3 ms 592 KB Output is correct
48 Correct 2 ms 592 KB Output is correct
49 Correct 2 ms 592 KB Output is correct
50 Correct 2 ms 592 KB Output is correct
51 Correct 2 ms 592 KB Output is correct
52 Runtime error 131 ms 17584 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -