oj.uz

Submission #1063521

# Submission time Handle Problem Language Result Execution time Memory
1063521 2024-08-17T19:51:28 Z PotatoTheWarriorFRTT Bulldozer (JOI17_bulldozer) C++14
0 / 100
 34 ms 856 KB 
#include <bits/stdc++.h>
using namespace std;
 
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;
    vector<Point> points;
    for(int i=0;i<n;i++) {
        Point p;
        long long x, y, w;
        cin >> p.first.first >> p.first.second >> p.second.first;
        points.push_back(p);
    }
    if(n==1) {
        cout << max(0LL, points[0].second.first) << endl;
        return;
    }
    ll ans = 0;
    for(int k=0;k<n;k++) {
        points[k].second.second = points[k].first.second;
    }
    sort(points.begin(), points.end(), comp);
    vector<ll> vals1;
    for(int k=0;k<n;k++) {
        vals1.push_back(0);
        ll X = points[k].second.second;
        while(points[k].second.second == X) {
            vals1[vals1.size()-1]+=points[k].second.first;
            k++;
        }
        k--;
    }
    ans = max(ans, max_sub_sum(vals1));
    for(int k=0;k<n;k++) {
        points[k].second.second = points[k].first.first;
    }
    sort(points.begin(), points.end(), comp);
    vector<ll> vals2;
    for(int k=0;k<n;k++) {
        vals2.push_back(0);
        ll X = points[k].second.second;
        while(points[k].second.second == X) {
            vals2[vals2.size()-1]+=points[k].second.first;
            k++;
        }
        k--;
    }

    ans = max(ans, max_sub_sum(vals2));
    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};

            int X = dir.first;
            int Y = dir.second;
            dir.first = Y;
            dir.second = -X;
            if(dir.first != 0 || dir.second != 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 dksfjn;
    cin >> dksfjn;
    // }
}

Compilation message

bulldozer.cpp: In function 'll max_sub_sum(std::vector<long long int>&)':
bulldozer.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=1;i<=vals.size();i++) {
      |                 ~^~~~~~~~~~~~~
bulldozer.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<vals.size();i++) {
      |                 ~^~~~~~~~~~~~
bulldozer.cpp: In function 'void solve()':
bulldozer.cpp:32:19: warning: unused variable 'x' [-Wunused-variable]
   32 |         long long x, y, w;
      |                   ^
bulldozer.cpp:32:22: warning: unused variable 'y' [-Wunused-variable]
   32 |         long long x, y, w;
      |                      ^
bulldozer.cpp:32:25: warning: unused variable 'w' [-Wunused-variable]
   32 |         long long x, y, w;
      |                         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 348 KB Output is correct
2 Correct 29 ms 344 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 348 KB Output is correct
5 Correct 34 ms 348 KB Output is correct
6 Correct 29 ms 348 KB Output is correct
7 Correct 29 ms 348 KB Output is correct
8 Incorrect 31 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 348 KB Output is correct
2 Correct 29 ms 344 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 348 KB Output is correct
5 Correct 34 ms 348 KB Output is correct
6 Correct 29 ms 348 KB Output is correct
7 Correct 29 ms 348 KB Output is correct
8 Incorrect 31 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 348 KB Output is correct
2 Correct 29 ms 344 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 348 KB Output is correct
5 Correct 34 ms 348 KB Output is correct
6 Correct 29 ms 348 KB Output is correct
7 Correct 29 ms 348 KB Output is correct
8 Incorrect 31 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -