Submission #1063507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063507		medmdg	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	38 ms	596 KiB

bulldozer

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
#define pb(a) push_back(a)
using namespace std;
typedef long long ll;

 
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(){
    ll n;
    cin>>n;
    vector<vector<ll>> points(n);
    for(int i=0;i<n;i++){
        ll x,y,w;
        cin>>x>>y>>w;
        points[i]={x,y,w};
    }
    sort(points.begin(),points.end());
    vector<vector<ll>> temp;
    temp.pb(points[0]);
    ll ans=0;
    for(int i=1;i<n;i++){
        if(points[i][0]==points[i-1][0]&& points[i][1]==points[i-1][1]){
            temp.back()[2]+=points[i][2];
        }else temp.pb(points[i]);
    }
    points=temp;
    n=points.size();
    for(auto i:points)ans=max(ans,i[2]);
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ll derive[2]={points[i][0]-points[j][0],points[i][1]-points[j][1]};
            vector<vector<ll> > t(n);
            for(int k=0;k<n;k++){
                if(derive[0]==0){
                    t[k]={points[k][1],points[k][2]};
                }else{
                    t[k]={points[k][0]*derive[0]+points[i][1]*derive[1],points[k][2]};
                }
            }
            sort(t.begin(),t.end());
            vector<ll>vals;
            for(int k=0;k<n;k++) {
                vals.push_back(t[k][1]);
                ll X = t[k][0];
                k++;
                while(k<n && points[k][0] == X) {
                    vals.back()+=t[k][1];
                    k++;
                }
                k--;
            }
            ans = max(ans, max_sub_sum(vals));
        }
    }
    cout<<ans<<endl;
}
int main()
{
    solve();

    return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'll max_sub_sum(std::vector<long long int>&)':
bulldozer.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=1;i<=vals.size();i++) {
      |                 ~^~~~~~~~~~~~~
bulldozer.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<vals.size();i++) {
      |                 ~^~~~~~~~~~~~

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