oj.uz

Submission #1037369

# Submission time Handle Problem Language Result Execution time Memory
1037369 2024-07-28T15:31:11 Z ivaziva Art Exhibition (JOI18_art) C++14
0 / 100
 0 ms 348 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;
vector<long long> pozicije;

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++)
    {
        if (prvi.find(vec[i].first)==prvi.end()) {prvi[vec[i].first]=i;poslednji[vec[i].first]=i;}
        else poslednji[vec[i].first]=i;
    }
    for (auto&p:poslednji) pozicije.push_back(p.second);
    long long ans=pref[pozicije[0]];
    long long trenmaks=vec[1].first;
    for (long long i=1;i<pozicije.size();i++)
    {
        long long prvapoz=pozicije[i];
        long long poslednjapoz=prvi[vec[prvapoz].first];
        long long s=pref[prvapoz]-pref[poslednjapoz-1];
        ans=max(ans,s);
        long long val1=s-vec[prvapoz].first+pref[poslednjapoz-1]+trenmaks;
        ans=max(ans,val1);
        long long vrednost=vec[poslednjapoz-1].first;
        long long poz=prvi[vrednost]-1;
        trenmaks=max(trenmaks,vrednost-pref[poz]);
    }
    cout<<ans<<endl;
}

Compilation message

art.cpp: In function 'int main()':
art.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (long long i=1;i<pozicije.size();i++)
      |                        ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -