제출 #502972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502972		Kirill_Maglysh	Art Exhibition (JOI18_art)	C++17	100 / 100	197 ms	29116 KiB

art

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

#define fori(n) for(int i = 0; i < n; ++i)
#define forj(n) for(int j = 0; j < n; ++j)
#define forr(n) for(int i = n - 1; i >= 0; --i)
#define forEach(array) for(auto &item : array)
#define printSpace(a) cout << a << " "
#define printSpace2(a, b) cout << a << " " << b << " "
#define printSpace3(a, b, c) cout << a << " " << b << " " << c << " "
#define printSpace4(a, b, c, d) cout << a << " " << b << " " << c << " " << d <<" "
#define printSpace5(a, b, c, d, e) cout << a << " "<< b << " " << c << " " << d <<" " << e << " "
#define printSpace6(a, b, c, d, e, f) cout << a << " "<< b << " " << c << " " << d <<" "<< e << " " << f << " "
#define printLn(n) cout << n << '\n'
#define printNL() cout <<'\n'
#define print(n) cout << n

using namespace std;

typedef long long ll;

struct CompressedLetter {
    ll num;
    char letter;
};

ll readLL();

string readStr();

void resolve();

void resolveTest();

bool isPrime(ll n);

vector<bool> detectPrimes(ll n);

ll minPosInArray(const vector<ll> &nums);

ll maxPosInArray(const vector<ll> &nums);

ll minValInArray(const vector<ll> &nums);

ll maxValInArray(const vector<ll> &nums);

vector<ll> calcPrefixSum(const vector<ll> &nums);

vector<ll> calcSuffixSum(const vector<ll> &nums);

vector<ll> getDigits(ll n);

ll sumNumRange(ll start, ll finish);

ll calcNumLength(ll n);

vector<CompressedLetter> processCompressedStr(const string &str);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    resolve();

    return 0;
}

void resolve() {
    ll num = readLL();
    vector<pair<ll, ll>> preProducts(num);
    forEach(preProducts) {
        item = {readLL(), readLL()};
    }

    sort(preProducts.begin(), preProducts.end());
    vector<pair<ll, ll>> products;
    products.push_back(preProducts[0]);
    for (int i = 1; i < preProducts.size(); ++i) {
        if (preProducts[i].first == products[products.size() - 1].first) {
            products[products.size() - 1].second += preProducts[i].second;
        } else {
            products.push_back(preProducts[i]);
        }
    }

    ll res = products[0].second;
    ll cur = products[0].second;
    for (ll i = 1; i < products.size(); ++i) {
        cur += products[i].second - (products[i].first - products[i - 1].first);
        if (cur < products[i].second) {
            cur = products[i].second;
        }

        res = max(res, cur);
    }

    printLn(res);
}

ll readLL() {
    ll num;
    cin >> num;
    return num;
}

string readStr() {
    string str;
    cin >> str;
    return str;
}

bool isPrime(ll n) {
    if (n == 0 || n == 1) {
        return false;
    }

    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

vector<bool> detectPrimes(ll n) {
    vector<bool> nums(n + 1, true);
    nums[0] = false;
    nums[1] = false;
    for (ll i = 2; i <= n; ++i) {
        if (nums[i]) {
            for (ll j = i * i; j <= n; j += i) {
                nums[j] = false;
            }
        }
    }

    return nums;
}

ll minPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] > nums[i]) {
            pos = i;
        }
    }

    return pos;
}

ll maxPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] < nums[i]) {
            pos = i;
        }
    }

    return pos;
}

vector<ll> getDigits(ll n) {
    vector<ll> digits;
    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }

    return digits;
}

vector<ll> calcPrefixSum(const vector<ll> &nums) {
    vector<ll> prefix(nums.size());
    prefix[0] = nums[0];
    for (ll i = 1; i < nums.size(); ++i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    return prefix;
}

vector<ll> calcSuffixSum(const vector<ll> &nums) {
    vector<ll> suffix(nums.size());
    suffix[nums.size() - 1] = nums[nums.size() - 1];
    for (ll i = (ll) nums.size() - 2; i >= 0; --i) {
        suffix[i] = suffix[i + 1] + nums[i];
    }

    return suffix;
}

ll sumNumRange(ll start, ll finish) {
    if (finish < start) {
        return 0;
    }

    if (start > 1) {
        return sumNumRange(1, finish) - sumNumRange(1, start - 1);
    }

    if (finish % 2 == 1L) {
        return sumNumRange(1, finish - 1) + finish;
    } else {
        return finish * (finish + 1) / 2;
    }
}

vector<CompressedLetter> processCompressedStr(const string &str) {
    vector<CompressedLetter> res;
    ll pos = 0;

    while (pos < str.length()) {
        ll numLength = 0;
        while ('0' <= str[pos] && str[pos] <= '9') {
            numLength++;
            pos++;
        }

        if (numLength == 0) {
            res.push_back({1, str[pos]});
        } else {
            res.push_back({stoi(str.substr(pos, numLength)), str[pos + numLength]});
        }

        pos += numLength + 1;
    }

    return res;
}

ll calcNumLength(ll n) {
    ll res = 0;
    while (n > 0) {
        n /= 10;
        res++;
    }

    return res;
}

ll minValInArray(const vector<ll> &nums) {
    return nums[minPosInArray(nums)];
}

ll maxValInArray(const vector<ll> &nums) {
    return nums[maxPosInArray(nums)];
}

컴파일 시 표준 에러 (stderr) 메시지

art.cpp: In function 'void resolve()':
art.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 1; i < preProducts.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
art.cpp:91:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (ll i = 1; i < products.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~~~~
art.cpp: In function 'll minPosInArray(const std::vector<long long int>&)':
art.cpp:146:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
art.cpp: In function 'll maxPosInArray(const std::vector<long long int>&)':
art.cpp:157:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
art.cpp: In function 'std::vector<long long int> calcPrefixSum(const std::vector<long long int>&)':
art.cpp:179:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
art.cpp: In function 'std::vector<CompressedLetter> processCompressedStr(const string&)':
art.cpp:216:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     while (pos < str.length()) {
      |            ~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50