제출 #478948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478948		ArkhamKnighty	Art Exhibition (JOI18_art)	C++14	0 / 100	1 ms	292 KiB

art

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50