Submission #1118147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118147		Pannda	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	1 ms	336 KiB

bulldozer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define int long long

using namespace std;

const int N = 2e3 + 5;

struct pt{
    int x, y, w, id;
};

vector<pt> a; int n;

int orientation(int x1, int y1, int x2, int y2, int x3, int y3){
    int o = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2);
    if(o > 0) return + 1;
    if(o < 0) return - 1;
    return 0;
}

int orientation(pt a, pt b, pt c){
    int o = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    if(o > 0) return + 1;
    if(o < 0) return - 1;
    return 0;
}
bool csub1(){
    if(n > 100) return false;
    for(int i = 0; i < n; i++) if(a[i].y != 0) return false;

    return true;
}
namespace sub1{
    void solve(){
        sort(a.begin(), a.end(), [](pt &x, pt &y){return x.x < y.x;});
        int ans = 0;
        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = i; j < n; j++){
                sum += a[i].w;
                ans = max(ans, sum);
            }
        }
        cout << ans << '\n';
    }
}

vector<pt> convexHull(vector<pt> a){
    sort(a.begin(), a.end(), [](pt x, pt y){
        return x.x < y.x || (x.x == y.x && x.y < y.y);
    });
    vector<pt> hull;

    for(int i = 0; i < a.size(); i++){
        while(hull.size() > 1 && orientation(hull[hull.size() - 2], hull.back(), a[i]) == 1) hull.pop_back();
        hull.push_back(a[i]);
    }
    for(int i = a.size() - 2; i >= 0; i--){
        while(hull.size() > 1 && orientation(hull[hull.size() - 2], hull.back(), a[i]) == 1) hull.pop_back();
        hull.push_back(a[i]);
    }
    hull.pop_back();
    return hull;
}


namespace nonlinear{
    void solve(){
        int ans = 0;
        vector<pt> hull = convexHull(a);

        for(int i = 0; i < hull.size(); i++){
            pt pivot = hull[i];

            vector<pt> b = a;
            swap(b[0], b[pivot.id]);
            sort(b.begin() + 1, b.end(), [&](const pt &x, const pt &y){
                int o = orientation(b[0], x, y);
                if(o >= 0) return true;
                return false;
            });
            int prefmn = 0, sum = b[0].w;
            ans = max(ans, sum);
            for(int i = 1; i < n; i++){
                sum += b[i].w;
                prefmn = min(prefmn, sum);
                ans = max(ans, sum - prefmn);
            }
        }
        cout << ans << '\n';
    }
}

namespace full{
    void solve(){
        int ans = 0;
        vector<pt> hull = convexHull(a);

        for(int i = 0; i < hull.size(); i++){
            pt pivot = hull[i];

            vector<pt> b = a;
            swap(b[0], b[pivot.id]);
            sort(b.begin() + 1, b.end(), [&](const pt &x, const pt &y){
                int o = orientation(b[0], x, y);
                if(o >= 0) return true;
                return false;
            });
            int prefmn = 0, sum = b[0].w;
            ans = max(ans, sum);
            for(int i = 1; i < n; i++){
                sum += b[i].w;
                prefmn = min(prefmn, sum);
                ans = max(ans, sum - prefmn);
            }
        }
        cout << ans << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "truffle"

    cin >> n;
    for(int i = 0; i < n; i++){
        int x, y, w; cin >> x >> y >> w;
        a.push_back({x, y, w, i});
    }

    if(csub1()) return sub1::solve(), 0;
    if(true) return nonlinear::solve(), 0;
//    full::solve();
    return 0;
}

/*
5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1

2
0 0 -1
1 0 -1
*/

Compilation message (stderr)

bulldozer.cpp: In function 'std::vector<pt> convexHull(std::vector<pt>)':
bulldozer.cpp:55:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
bulldozer.cpp: In function 'void nonlinear::solve()':
bulldozer.cpp:73:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < hull.size(); i++){
      |                        ~~^~~~~~~~~~~~~
bulldozer.cpp: In function 'void full::solve()':
bulldozer.cpp:100:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i = 0; i < hull.size(); i++){
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20