#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
const int MAXN = 2010 ;
using namespace std ;
struct Seg
{
long long soma[MAXN*4] ;
long long bestLeft[MAXN*4] ;
long long bestRight[MAXN*4] ;
long long bestSum[MAXN*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
void print(int pos, int l, int r )
{
if(l == r ) return (void)(printf("%d ", soma[pos] ) ) ;
print(pos<<1 , l, m(l,r) ) ;
print(pos<<1|1 , m(l,r)+1, r ) ;
}
void upd(int pos, int l, int r, int k, long long val ) //vamos de seg de setar?
{
if( l == r )
{
soma[pos] = val ;
bestLeft[pos] = bestRight[pos] = bestSum[pos] = max(val, 0LL ) ;
return ;
}
if( k <= m(l,r) ) upd(pos<<1 , l , m(l,r) , k, val ) ;
else upd(pos<<1|1 , m(l,r)+1, r, k, val ) ;
soma[pos] = soma[pos<<1] + soma[pos<<1|1] ;
bestLeft[pos] = max(bestLeft[pos<<1|1] , soma[pos<<1|1] + bestLeft[pos<<1] ) ;
bestRight[pos] = max(bestRight[pos<<1], soma[pos<<1] + bestRight[pos<<1|1] ) ;
bestSum[pos] = bestLeft[pos<<1] + bestRight[pos<<1|1] ;
bestSum[pos] = max(bestSum[pos<<1] ,max(bestSum[pos] , bestSum[pos<<1|1] ) ) ;
}
long long getAns() { return bestSum[1] ; }
} seg ;
int n ;
int x[MAXN], y[MAXN] ;
int pos[MAXN] ;
long long w[MAXN] ;
int getFakeQuadrant(int i, int j )
{
if( x[i] > x[j] ) return 0 ;
if(x[i] == x[j] ) return 1 ;
return 2 ;
}
struct Event
{
int i , j ;
Event(int i = 0 , int j = 0 ) : i(i) , j(j) {}
bool operator < (Event other) const
{
/* Tenho certeza que:
i) y[i] > y[j]
ii) y[i] == y[j] && x[i] > x[j]
O numerador sempre vai ser positivo ou zero
*/
pair<int,int> mySlope = make_pair(y[i]-y[j], x[i]-x[j] ) ;
pair<int,int> otherSlope = make_pair(y[other.i]-y[other.j], x[other.i]-x[other.j] ) ;
int myFakeQuadrant = getFakeQuadrant(i,j) ;
int otherFakeQuadrant = getFakeQuadrant(other.i , other.j ) ;
if(myFakeQuadrant != otherFakeQuadrant )
return myFakeQuadrant < otherFakeQuadrant ;
//Remember the denominators can be negative
//And, therefore, the comparison will be weird
if( mySlope.first * otherSlope.second == mySlope.second * otherSlope.first )
{
//This will work even if there isn't a slope at all
return make_pair(y[i], y[j] ) > make_pair(y[other.i], y[other.j] ) ;
}
if(mySlope.second < 0 )
{
mySlope.first = -mySlope.first ;
mySlope.second = -mySlope.second ;
}
if(otherSlope.second < 0 )
{
otherSlope.first = -otherSlope.first ;
otherSlope.second = -otherSlope.second ;
}
return mySlope.first * otherSlope.second < mySlope.second * otherSlope.first ;
}
} ;
bool isEqual(Event a, Event b )
{
pair<int,int> slope_a = make_pair( y[a.i] - y[a.j] , x[a.i] - x[a.j] ) ;
pair<int,int> slope_b = make_pair( y[b.i] - y[b.j], x[b.i] - x[b.j] ) ;
if( getFakeQuadrant(a.i, a.j ) != getFakeQuadrant(b.i, b.j ) )
return false ;
return slope_a.first * slope_b.second == slope_a.second * slope_b.first ;
}
int main()
{
scanf("%d", &n ) ;
for(int i = 1 ; i <= n ; i++ ) scanf("%d %d %lld", &x[i], &y[i] , &w[i] ) ;
vector<int> initialSort(n) ;
iota(all(initialSort),1) ;
sort(all(initialSort), [&](int i, int j ) {
if( y[i] != y[j] ) return y[i] > y[j] ;
return x[i] > x[j] ;
} ) ;
// for(int i = 0 ; i < n ; i++ ) cout << char(initialSort[i] + 'A' - 1 ) << " " ;
// cout << endl ;
vector<Event> sweep ;
for(int i = 0 ; i < n ; i++ ) pos[ initialSort[i] ] = i+1 ;
for(int i = 0 ; i < n ; i++ )
for(int j = i+1 ; j < n ; j++ )
sweep.push_back(Event(initialSort[i],initialSort[j]) ) ;
sort(all(sweep));
//Depois eu crio a seg, vamos tentar entender os eventos primeiro
// for(auto e : sweep ) cout << char(e.i + 'A'-1) << " " << char(e.j+'A'-1) << endl ;
for(int i = 1 ; i <= n ; i++ ) seg.upd(1,1,n, pos[i] , w[i] ) ;
long long ans = 0LL ;
ans = max(ans, seg.getAns() ) ;
for(int i = 0 ; i < sz(sweep ) ; )
{
//initiating batch process
int j = i ;
while( j < sz(sweep) && isEqual(sweep[i], sweep[j] ) )
{
int u = sweep[j].i ;
int v = sweep[j].j ;
seg.upd(1 , 1 , n , pos[u] , w[v] ) ;
seg.upd(1,1,n, pos[v], w[u] ) ;
swap(pos[u], pos[v] ) ;
j++ ;
}
i = j ;
/*cout << "After some lines"<< endl ;
seg.print(1,1,n) ;
cout << endl ; */
ans = max(ans, seg.getAns() ) ;
}
printf("%lld\n", ans ) ;
}
Compilation message
bulldozer.cpp: In member function 'void Seg::print(int, int, int)':
bulldozer.cpp:23:38: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
23 | if(l == r ) return (void)(printf("%d ", soma[pos] ) ) ;
| ~^ ~~~~~~~~~
| | |
| int long long int
| %lld
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
136 | scanf("%d", &n ) ;
| ~~~~~^~~~~~~~~~~
bulldozer.cpp:137:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | for(int i = 1 ; i <= n ; i++ ) scanf("%d %d %lld", &x[i], &y[i] , &w[i] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
512 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
