#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000000+7;
typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> Point;
bool comp(Point p1, Point p2) {
return p1.second.second < p2.second.second;
}
ll max_sub_sum(vector<ll> &vals) {
ll S[vals.size()+1];
ll M[vals.size()+1];
S[0] = 0;
M[0] = 0;
for(int i=1;i<=vals.size();i++) {
S[i] = S[i-1]+vals[i-1];
M[i] = min(M[i-1], S[i]);
}
ll ans = 0;
for(int i=0;i<vals.size();i++) {
ans = max(ans, S[i+1] - M[i+1]);
}
return ans;
}
void solve() {
int n; cin >> n;
if(n==0) {
cout << 0 << endl;
return;
}
vector<Point> points;
for(int i=0;i<n;i++) {
Point p;
long long x, y, w;
cin >> x >> y >> w;
p.first.first = x;
p.first.second = y;
p.second.first = w;
points.push_back(p);
}
ll ans = max(0LL, points[0].second.first);
bool considered = false;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
pair<ll, ll> dir = {points[i].first.first - points[j].first.first, points[i].first.second - points[j].first.second};
if(dir.first != 0 || dir.second != 0 || !considered) {
if(dir.first == 0 && dir.second == 0) {
considered = true;
dir = {1, 0};
}
for(int k=0;k<n;k++) {
points[k].second.second = dir.first * points[k].first.first + dir.second * points[k].first.second;
}
sort(points.begin(), points.end(), comp);
vector<ll> vals;
for(int k=0;k<n;k++) {
vals.push_back(0);
ll X = points[k].second.second;
while(points[k].second.second == X) {
vals[vals.size()-1]+=points[k].second.first;
k++;
}
k--;
}
ans = max(ans, max_sub_sum(vals));
}
}
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
// cin >> t;
// while (t--)
solve();
char sdhfn;
cin >> sdhfn;
}
Compilation message
bulldozer.cpp: In function 'll max_sub_sum(std::vector<long long int>&)':
bulldozer.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=1;i<=vals.size();i++) {
| ~^~~~~~~~~~~~~
bulldozer.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<vals.size();i++) {
| ~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:78:9: warning: unused variable 't' [-Wunused-variable]
78 | int t;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
348 KB |
Output is correct |
| 2 |
Correct |
14 ms |
348 KB |
Output is correct |
| 3 |
Correct |
14 ms |
464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
468 KB |
Output is correct |
| 5 |
Correct |
14 ms |
464 KB |
Output is correct |
| 6 |
Correct |
15 ms |
348 KB |
Output is correct |
| 7 |
Correct |
14 ms |
348 KB |
Output is correct |
| 8 |
Correct |
15 ms |
472 KB |
Output is correct |
| 9 |
Correct |
14 ms |
472 KB |
Output is correct |
| 10 |
Correct |
14 ms |
464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
360 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
348 KB |
Output is correct |
| 2 |
Correct |
29 ms |
348 KB |
Output is correct |
| 3 |
Correct |
29 ms |
348 KB |
Output is correct |
| 4 |
Correct |
32 ms |
348 KB |
Output is correct |
| 5 |
Correct |
29 ms |
348 KB |
Output is correct |
| 6 |
Correct |
30 ms |
348 KB |
Output is correct |
| 7 |
Correct |
29 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
348 KB |
Output is correct |
| 2 |
Correct |
29 ms |
348 KB |
Output is correct |
| 3 |
Correct |
29 ms |
348 KB |
Output is correct |
| 4 |
Correct |
32 ms |
348 KB |
Output is correct |
| 5 |
Correct |
29 ms |
348 KB |
Output is correct |
| 6 |
Correct |
30 ms |
348 KB |
Output is correct |
| 7 |
Correct |
29 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
348 KB |
Output is correct |
| 2 |
Correct |
29 ms |
348 KB |
Output is correct |
| 3 |
Correct |
29 ms |
348 KB |
Output is correct |
| 4 |
Correct |
32 ms |
348 KB |
Output is correct |
| 5 |
Correct |
29 ms |
348 KB |
Output is correct |
| 6 |
Correct |
30 ms |
348 KB |
Output is correct |
| 7 |
Correct |
29 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
29 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
348 KB |
Output is correct |
| 2 |
Correct |
14 ms |
348 KB |
Output is correct |
| 3 |
Correct |
14 ms |
464 KB |
Output is correct |
| 4 |
Correct |
14 ms |
468 KB |
Output is correct |
| 5 |
Correct |
14 ms |
464 KB |
Output is correct |
| 6 |
Correct |
15 ms |
348 KB |
Output is correct |
| 7 |
Correct |
14 ms |
348 KB |
Output is correct |
| 8 |
Correct |
15 ms |
472 KB |
Output is correct |
| 9 |
Correct |
14 ms |
472 KB |
Output is correct |
| 10 |
Correct |
14 ms |
464 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
360 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
29 ms |
348 KB |
Output is correct |
| 17 |
Correct |
29 ms |
348 KB |
Output is correct |
| 18 |
Correct |
29 ms |
348 KB |
Output is correct |
| 19 |
Correct |
32 ms |
348 KB |
Output is correct |
| 20 |
Correct |
29 ms |
348 KB |
Output is correct |
| 21 |
Correct |
30 ms |
348 KB |
Output is correct |
| 22 |
Correct |
29 ms |
348 KB |
Output is correct |
| 23 |
Incorrect |
29 ms |
348 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
