oj.uz

Submission #1037370

# Submission time Handle Problem Language Result Execution time Memory
1037370 2024-07-28T15:38:01 Z ivaziva Art Exhibition (JOI18_art) C++14
50 / 100
 335 ms 16560 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 5001

long long n;
vector<pair<long long,long long>> vec;
long long pref[MAXN];
map<long long,long long> poslednji;
map<long long,long long> prvi;

int main()
{
    cin>>n;
    vec.push_back({0,0});
    for (long long i=1;i<=n;i++)
    {
        long long a,b;cin>>a>>b;
        vec.push_back({a,b});
    }
    sort(vec.begin(),vec.end());
    pref[0]=0;
    for (long long i=1;i<=n;i++) pref[i]=pref[i-1]+vec[i].second;
    for (long long i=1;i<=n;i++)
    {
        poslednji[vec[i].first]=i;
        if (prvi.find(vec[i].first)==prvi.end()) prvi[vec[i].first]=i;
    }
    long long ans=pref[poslednji[vec[1].first]];
    long long trenmaks=vec[1].first;
    for (auto&p:poslednji)
    {
        if (p.first==vec[1].first) continue;
        long long desno=p.second,a3=p.first;
        long long levo=prvi[a3];
        long long s=pref[desno]-pref[levo-1];
        ans=max(ans,s);
        long long i=levo-1;
        long long val=s-a3+pref[i]+trenmaks;
        ans=max(ans,val);
        trenmaks=max(trenmaks,a3-pref[i]);
    }
    cout<<ans<<endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1116 KB Output is correct
28 Correct 5 ms 976 KB Output is correct
29 Correct 5 ms 1196 KB Output is correct
30 Correct 5 ms 1116 KB Output is correct
31 Correct 5 ms 1116 KB Output is correct
32 Correct 5 ms 1116 KB Output is correct
33 Correct 5 ms 952 KB Output is correct
34 Correct 5 ms 1076 KB Output is correct
35 Correct 5 ms 1116 KB Output is correct
36 Correct 7 ms 1048 KB Output is correct
37 Correct 5 ms 1116 KB Output is correct
38 Correct 5 ms 1116 KB Output is correct
39 Correct 5 ms 1116 KB Output is correct
40 Correct 5 ms 1116 KB Output is correct
41 Correct 5 ms 1116 KB Output is correct
42 Correct 5 ms 1116 KB Output is correct
43 Correct 5 ms 1180 KB Output is correct
44 Correct 5 ms 1116 KB Output is correct
45 Correct 5 ms 1116 KB Output is correct
46 Correct 5 ms 1144 KB Output is correct
47 Correct 5 ms 1116 KB Output is correct
48 Correct 5 ms 1116 KB Output is correct
49 Correct 5 ms 1112 KB Output is correct
50 Correct 5 ms 1116 KB Output is correct
51 Correct 5 ms 1116 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1116 KB Output is correct
28 Correct 5 ms 976 KB Output is correct
29 Correct 5 ms 1196 KB Output is correct
30 Correct 5 ms 1116 KB Output is correct
31 Correct 5 ms 1116 KB Output is correct
32 Correct 5 ms 1116 KB Output is correct
33 Correct 5 ms 952 KB Output is correct
34 Correct 5 ms 1076 KB Output is correct
35 Correct 5 ms 1116 KB Output is correct
36 Correct 7 ms 1048 KB Output is correct
37 Correct 5 ms 1116 KB Output is correct
38 Correct 5 ms 1116 KB Output is correct
39 Correct 5 ms 1116 KB Output is correct
40 Correct 5 ms 1116 KB Output is correct
41 Correct 5 ms 1116 KB Output is correct
42 Correct 5 ms 1116 KB Output is correct
43 Correct 5 ms 1180 KB Output is correct
44 Correct 5 ms 1116 KB Output is correct
45 Correct 5 ms 1116 KB Output is correct
46 Correct 5 ms 1144 KB Output is correct
47 Correct 5 ms 1116 KB Output is correct
48 Correct 5 ms 1116 KB Output is correct
49 Correct 5 ms 1112 KB Output is correct
50 Correct 5 ms 1116 KB Output is correct
51 Correct 5 ms 1116 KB Output is correct
52 Runtime error 335 ms 16560 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -