oj.uz

Submission #478948

# Submission time Handle Problem Language Result Execution time Memory
478948 2021-10-09T07:41:20 Z ArkhamKnighty Art Exhibition (JOI18_art) C++14
0 / 100
 1 ms 292 KB 
#include <iostream>
#include <vector>
#define pll pair < long long, long long >
#include <algorithm>

using namespace std;

vector < pll > v;
vector < long long > sum;

int main()
{
    int n;
    long long x, y;

    cin >> n;
    sum.push_back(0);
    v.push_back({0,0});
    for(int i = 1 ; i <= n ; i++)
    cin >> x >> y, v.push_back({x, y}),
    sum.push_back(y);

    sort(v.begin() + 1, v.end());

    for(int i = 1 ; i <= n ; i++)
        sum[i] = sum[i-1] + v[i].second;

    int left = 1;
    long long maxx = -(1<<30);
    for(int i = 1 ; i <= n ; i++)
    {
        while(left < i &&
        (sum[i] - sum[left-1]) - (v[i].first-v[left].first)
    < (sum[i] - sum[left]) - (v[i].first-v[left+1].first) ) left++;

        //cout << "AICI "<< left << ' ' << i << ' ' <<
        //(sum[i] - sum[left-1]) - (v[i].first-v[left].first) << '\n';

        maxx = max(maxx,
                  (sum[i] - sum[left-1]) - (v[i].first-v[left].first));

        /*if(i < n)
        maxx = max(maxx,
                   (sum[i+1] - sum[left-1]) - (v[i+1].first-v[left-1].first) );*/
    }

    cout << maxx << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -