Submission #105021

#	Time	Username	Problem	Language	Result	Execution time	Memory
105021		YottaByte	Cake 3 (JOI19_cake3)	C++14	24 / 100	307 ms	768 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

cake3

#include <bits/stdc++.h> using namespace std; #define int long long #define fr first #define sc second #define pii pair < int, int > const int N = 4001; int n, k; long long ans = -1e18; pii a[N]; multiset < int > s; bool cmp(pii a, pii b) { if(a.sc < b.sc) return true; else if(a.sc == b.sc) return (a.fr < b.fr); else return false; } main() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i].fr >> a[i].sc; sort(a + 1, a + n + 1, &cmp); long long res = 0; for(int i = 1; i <= n; i++) { res = a[i].fr; while(s.size()) { s.erase(s.begin()); } for(int j = i + 1; j <= n; j++) { res += a[j].fr; if(s.size() > k - 2) { res -= *s.begin(); s.erase(s.begin()); } if(s.size() == k - 2) ans = max(res - 2ll * (a[j].sc - a[i].sc), ans); s.insert( a[j].fr ); } } cout << ans << endl; } /*** 94 22 17729830 195028137 17729832 195028150 17729830 195028178 17729832 195028140 17729832 195028118 17729836 195028176 17729835 195028180 17729829 195028198 17729829 195028141 17729835 195028132 17729834 195028115 17729829 195028197 17729829 195028160 17729829 195028137 17729834 195028161 17729836 195028115 17729829 195028107 17729834 195028170 17729832 195028132 17729829 195028159 17729833 195028183 17729836 195028178 17729834 195028201 17729830 195028108 17729831 195028145 17729832 195028202 17729829 195028191 17729832 195028150 17729829 195028180 17729835 195028118 17729829 195028176 17729830 195028176 17729834 195028167 17729828 195028160 17729833 195028202 17729829 195028188 17729834 195028107 17729836 195028202 17729830 195028150 17729828 195028137 17729836 195028188 17729831 195028106 17729835 195028176 17729835 195028140 17729834 195028132 17729836 195028137 17729834 195028107 17729834 195028124 17729833 195028137 17729834 195028112 17729834 195028161 17729834 195028154 17729835 195028132 17729832 195028132 17729837 195028202 17729834 195028127 17729830 195028152 17729835 195028150 17729835 195028111 17729829 195028161 17729832 195028137 17729830 195028172 17729829 195028162 17729834 195028161 17729835 195028150 17729834 195028162 17729832 195028114 17729830 195028183 17729829 195028181 17729835 195028113 17729829 195028107 17729835 195028180 17729834 195028145 17729829 195028186 17729837 195028181 17729829 195028159 17729835 195028126 17729836 195028146 17729834 195028118 17729835 195028180 17729832 195028130 17729830 195028172 17729829 195028189 17729834 195028190 17729829 195028150 17729832 195028147 17729833 195028168 17729834 195028120 17729829 195028199 17729834 195028118 17729835 195028178 17729828 195028194 17729837 195028191 17729837 195028170 ***/

Compilation message (stderr)

cake3.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size() > k - 2) {
       ~~~~~~~~~^~~~~~~
cake3.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size() == k - 2)
       ~~~~~~~~~^~~~~~~~

Subtask 15 / 5

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 219 / 19

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 30 / 76

#	Verdict	Execution time	Memory	Grader output
Fetching results...