Submission #1138055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138055		SmuggingSpun	Pinball (JOI14_pinball)	C++20	100 / 100	190 ms	22720 KiB

pinball

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const ll INF = 1e18;
int n, m;
namespace sub1{
	void solve(){
		vector<int>a(n), b(n), c(n), d(n);
		for(int i = 0; i < n; i++){
			cin >> a[i] >> b[i] >> c[i] >> d[i];
		}
		ll ans = INF;
		for(int mask = (1 << n) - 1; mask > -1; mask--){
			ll sum = 0;
			for(int i = 0; i < n; i++){
				if(1 << i & mask){
					sum += d[i];
				}
			}
			if(sum < ans){
				int pat = -1;
				for(int i = 1; i <= m; i++){
					int x = i;
					for(int j = 0; j < n; j++){
						if((1 << j & mask) && a[j] <= x && b[j] >= x){
							x = c[j];
						}
					}
					if(pat == -1){
						pat = x;
					}
					else if(pat != x){
						sum = -1;
						break;
					}
				}
				if(sum != -1){
					ans = sum;
				}
			}
		}
		cout << (ans == INF ? -1 : ans);
	}
}
namespace sub2{
	const int lim = 205;
	int a[lim], b[lim], c[lim], d[lim];
	ll dp[lim * 3][lim * 3];
	pair<int, int>overlap(pair<int, int>a, pair<int, int>b){
		return a.second < b.first || b.second < a.first ? make_pair(-1, -1) : make_pair(min(a.first, b.first), max(a.second, b.second));
	}
	void solve(){
		vector<int>point = {1, m};
		memset(dp, 0x0f, sizeof(dp));
		for(int i = 1; i <= n; i++){
			cin >> a[i] >> b[i] >> c[i] >> d[i];
			point.emplace_back(a[i]);
			point.emplace_back(b[i]);
			point.emplace_back(c[i]);
		}
		sort(point.begin(), point.end());
		point.resize(unique(point.begin(), point.end()) - point.begin());
		for(int i = (m = point.size()) - 1; i > -1; i--){
			dp[i][i] = 0;
		}
		for(int i = n; i > 0; i--){
			c[i] = lower_bound(point.begin(), point.end(), c[i]) - point.begin();
			minimize(dp[a[i] = lower_bound(point.begin(), point.end(), a[i]) - point.begin()][b[i] = lower_bound(point.begin(), point.end(), b[i]) - point.begin()], ll(d[i]));
			for(int l = 0; l < m; l++){
				for(int r = l; r < m; r++){
					pair<int, int>current = overlap(make_pair(l, r), make_pair(a[i], b[i]));
					if(current.first != -1 && c[i] >= l && c[i] <= r){
						minimize(dp[current.first][current.second], dp[l][r] + d[i]);
					}
				}
			}
			for(int len = 1; len < m; len++){
				for(int r = len; r < m; r++){
					int l = r - len;
					minimize(dp[l][r - 1], dp[l][r]);
					minimize(dp[l + 1][r], dp[l][r]);
				}
			}
		}
		cout << (dp[0][m - 1] > INF ? -1 : dp[0][m - 1]);
	}
}
namespace sub3{
	const int lim = 1e3 + 5;
	int a[lim], b[lim], c[lim], d[lim];
	ll ans = INF, dp[lim][2];
	void solve(){
		for(int i = 1; i <= n; i++){
			cin >> a[i] >> b[i] >> c[i] >> d[i];
		}		
		vector<int>p(n);
		iota(p.begin(), p.end(), 1);
		sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
			return a[i] < a[j];
		});
		memset(dp, 0x0f, sizeof(dp));
		for(int i = 0; i < n; i++){
			if(a[p[i]] == 1){
				dp[p[i]][0] = 0;
			}			
			else{
				for(int j = i - 1; j > -1; j--){
					if(p[j] < p[i] && c[p[j]] >= a[p[i]] && c[p[j]] <= b[p[i]]){
						minimize(dp[p[i]][0], dp[p[j]][0]);
					}
				}
			}
			dp[p[i]][0] += d[p[i]];
		}
		reverse(p.begin(), p.end());
		for(int i = 0; i < n; i++){
			if(b[p[i]] == m){
				dp[p[i]][1] = 0;
			}
			else{
				for(int j = i - 1; j > -1; j--){
					if(p[j] < p[i] && c[p[j]] >= a[p[i]] && c[p[j]] <= b[p[i]]){
						minimize(dp[p[i]][1], dp[p[j]][1]);
					}
				}
			}
			minimize(ans, dp[p[i]][0] + dp[p[i]][1]);
			dp[p[i]][1] += d[p[i]];
		}
		cout << (ans == INF ? -1 : ans);
	}
}
namespace sub4{
	const int lim = 1e5 + 5;
	const int LIM = 3e5 + 5;
	ll ans = INF;
	int a[lim], b[lim], c[lim], d[lim];
	struct SegmentTree{
		ll st[LIM << 2];
		SegmentTree(){
			memset(st, 0x0f, sizeof(st));
		}
		void update(int id, int l, int r, int p, ll x){
			if(l == r){
				minimize(st[id], x);
				return;
			}
			int m = (l + r) >> 1;
			if(m < p){
				update(id << 1 | 1, m + 1, r, p, x);
			}
			else{
				update(id << 1, l, m, p, x);
			}
			st[id] = min(st[id << 1], st[id << 1 | 1]);
		}	
		ll get(int id, int l, int r, int u, int v){
			if(l > v || r < u){
				return INF;
			}
			if(u <= l && v >= r){
				return st[id];
			}
			int m = (l + r) >> 1;
			return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
		}
	};
	SegmentTree left, right;
	vector<int>point;
	int compress(int i){
		return lower_bound(point.begin(), point.end(), i) - point.begin() + 1;
	}
	void solve(){
		for(int i = 1; i <= n; i++){
			cin >> a[i] >> b[i] >> c[i] >> d[i];
			point.emplace_back(a[i]);
			point.emplace_back(b[i]);
			point.emplace_back(c[i]);
		}
		sort(point.begin(), point.end());
		point.resize(unique(point.begin(), point.end()) - point.begin());
		m = point.size();
		for(int i = 1; i <= n; i++){
			b[i] = compress(b[i]);
			ll L = ((a[i] = compress(a[i])) == 1 ? 0 : left.get(1, 1, m, a[i], b[i])), R = (b[i] == m ? 0 : right.get(1, 1, m, a[i], b[i]));
			minimize(ans, L + (R += d[i]));
			left.update(1, 1, m, c[i] = compress(c[i]), L + d[i]);
			right.update(1, 1, m, c[i], R);
		}
		cout << (ans == INF ? -1 : ans);
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(n <= 10 && m <= 1000){
		sub1::solve();
	}
	else if(n <= 200){
		sub2::solve();
	}
	else if(n <= 1000){
		sub3::solve();
	}
	else{
		sub4::solve();
	}
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:202:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49