Untitled
unknown
plain_text
a year ago
1.6 kB
9
Indexable
#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; }
Editor is loading...
Leave a Comment