#include #include short used[1000]; unsigned long long int sol = 0; void findSmaller(int cost[], int out[], int in, int x, int n) { int i, j, max = -1; for (i = 0; i < n; i++) { if ((out[i] < in) && (out[i] > max) && (!used[i])) { max = out[i]; j = i; if (out[i] == in - 1) break; } } if (max != -1) { sol -= out[j] * cost[x]; used[j] = 1; } } int partition( int a[], int b[], int c[], int l, int r) { int pivot, i, j, t; pivot = a[l]; i = l; j = r+1; while( 1) { do ++i; while( a[i] <= pivot && i <= r ); do --j; while( a[j] > pivot ); if( i >= j ) break; t = a[i]; a[i] = a[j]; a[j] = t; t = b[i]; b[i] = b[j]; b[j] = t; t = c[i]; c[i] = c[j]; c[j] = t; } t = a[l]; a[l] = a[j]; a[j] = t; t = b[l]; b[l] = b[j]; b[j] = t; t = c[l]; c[l] = c[j]; c[j] = t; return j; } void quickSort( int a[], int b[], int c[], int l, int r) { int j; if( l < r ) { // divide and conquer j = partition( a, b, c, l, r); quickSort( a, b, c, l, j-1); quickSort( a, b, c, j+1, r); } } int main() { int n, out[1000], in[1000], cost[1000], i; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d%d", &out[i], &in[i], &cost[i]); sol += in[i] * cost[i]; used[i] = 0; } quickSort(cost, out, in, 0, n-1); for (i = n-1; i >= 0; i--) { findSmaller(cost, out, in[i], i, n); } printf("%llu\n", sol); return 0; }