# Untitled

unknown
plain_text
a month ago
1.6 kB
5
Indexable
Never
```#include <iostream>

#include <limits>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>

typedef long long ll;

using namespace std;

typedef pair<ll, ll> pii;

ll N;

const int MAXN = 101;
const int MAXZ = 1e5+5;
ll X[MAXN], Y[MAXN], Z[MAXN];

const ll INF = 1e18;

// at pos, seat
ll dp[MAXN][MAXZ];

void solve() {
cin>>N;

for(int i=0; i<MAXN; i++) {
for(int j=0; j<MAXZ; j++) {
dp[i][j] = INF;
}
}

ll t_seats = 0;
// cost, reward
vector<pii> arr;
ll tot_seats = 0;
for(int i=0; i<N; i++) {
cin>>X[i]>>Y[i]>>Z[i];
tot_seats += Z[i];

if(X[i] > Y[i]) {
t_seats += Z[i];
// arr.push_back({0, Z[i]});
} else {
ll half =  (Y[i] + X[i] + 1 ) / 2;
ll need = half - X[i];
arr.push_back({need, Z[i]});
}
}

ll need_seats = max(0LL, ((tot_seats + 1) / 2) - t_seats);

// ll need_seats = (tot_seats + 1) / 2;

dp[0][0] = 0;

for(int i=0; i<N; i++) {
for(int j=0; j<MAXZ; j++) {
ll next_seat = arr[i].second + j;
if(next_seat < MAXZ) {
dp[i+1][next_seat] = min(dp[i+1][next_seat], dp[i][j] + arr[i].first);
}
dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
}
}

ll ans = INF;
for(int i=0; i<MAXN; i++) {
for(int j=need_seats; j<MAXZ; j++) {
ans = min(ans, dp[i][j]);
}
}

cout<<ans<<endl;
}

int main() {
// speed up
ios::sync_with_stdio(0);
cin.tie(0);

solve();

return 0;
}
```