제출 #923521

#제출 시각아이디문제언어결과실행 시간메모리
923521danikoynovCake 3 (JOI19_cake3)C++14
0 / 100
12 ms38132 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 2e5 + 10; int n, m; pair < int, int > a[maxn]; void input() { cin >> n >> m; for (int i = 1; i <= n; i ++) { cin >> a[i].first >> a[i].second; } } bool cmp_second(pair < int, int > f, pair < int, int > s) { return f.second < s.second; } ll inf = 1e18; struct block { vector < ll > to_left, to_right; void init(int idx) { to_left.resize(2); to_right.resize(2); to_left[0] = -inf; to_left[1] = a[idx].first + 2 * a[idx].second; to_right[0] = -inf; to_right[1] = a[idx].first - 2 * a[idx].second; } }; block tree[4 * maxn]; ll result; void conquer(int t, int l, int r) { int len = r - l + 1; if (len >= m) { for (int i = 1; i <= m; i ++) { if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size()) { ll sum = tree[t * 2].to_left[i] + tree[t * 2 + 1].to_right[m - i]; if (sum > result) { //cout << l << " : " << r << " " << sum << endl; result = sum; } } } } vector < ll > lf_val, rf_val; int mid = (l + r) / 2; for (int i = l; i <= mid; i ++) lf_val.push_back(a[i].first); for (int i = mid + 1; i <= r; i ++) rf_val.push_back(a[i].first); sort(lf_val.begin(), lf_val.end()); reverse(lf_val.begin(), lf_val.end()); sort(rf_val.begin(), rf_val.end()); reverse(rf_val.begin(), rf_val.end()); lf_val.insert(lf_val.begin(), (ll)0); rf_val.insert(rf_val.begin(), (ll)0); for (int i = 1; i < lf_val.size(); i ++) lf_val[i] += lf_val[i - 1]; for (int i = 1; i < rf_val.size(); i ++) rf_val[i] += rf_val[i - 1]; tree[t].to_left.resize(r - l + 2, -inf); for (int i = 1; i < tree[t * 2].to_left.size(); i ++) tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[i]); for (int i = 1; i < tree[t * 2 + 1].to_left.size(); i ++) tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2 + 1].to_left[i]); //cout << "--------------------" << endl; //cout << "range " << l << " " << r << endl; for (int i = 1; i <= len; i ++) { for (int j = 1; j <= min((int)(tree[t * 2].to_left.size() - 1), i); j ++ ) { if (i - j < rf_val.size()) tree[t].to_left[i] = max(tree[t].to_left[i], tree[t * 2].to_left[j] + rf_val[i - j]); } } tree[t].to_right.resize(r - l + 2, -inf); for (int i = 1; i < tree[t * 2].to_right.size(); i ++) tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2].to_right[i]); for (int i = 1; i < tree[t * 2 + 1].to_right.size(); i ++) tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[i]); for (int i = 1; i <= len; i ++) { for (int j = 1; j <= min((int)tree[t * 2 + 1].to_right.size() - 1, i); j ++) { if (i - j < lf_val.size()) tree[t].to_right[i] = max(tree[t].to_right[i], tree[t * 2 + 1].to_right[j] + lf_val[i - j]); } } //for (int i = 0; i < tree[t].to_left.size(); i ++) // cout << tree[t].to_right[i] << " "; //cout << endl; } void divide(int t, int l, int r) { if (l == r) { tree[t].init(l); if (m == 1) result = max(result, (ll)a[l].first); return; } int mid = (l + r) / 2; divide(t * 2, l, mid); divide(t * 2 + 1, mid + 1, r); conquer(t, l, r); } void do_math() { sort(a + 1, a + n + 1, cmp_second); divide(1, 1, n); cout << result << endl; } void solve() { input(); do_math(); } int main() { solve(); return 0; }

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

cake3.cpp: In function 'void conquer(int, int, int)':
cake3.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:66:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             if (i < tree[t * 2].to_left.size() && m - i < tree[t * 2 + 1].to_right.size())
      |                                                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 1; i < lf_val.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
cake3.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i < rf_val.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
cake3.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 1; i < tree[t * 2].to_left.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 1; i < tree[t * 2 + 1].to_left.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             if (i - j < rf_val.size())
      |                 ~~~~~~^~~~~~~~~~~~~~~
cake3.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 1; i < tree[t * 2].to_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 1; i < tree[t * 2 + 1].to_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             if (i - j < lf_val.size())
      |                 ~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...