| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 295287 |
2020-09-09T15:05:04 Z |
임성재(#5809) |
치료 계획 (JOI20_treatment) |
C++17 |
|
161 ms |
3192 KB |
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
int n, m;
int t[100010];
int l[100010];
int r[100010];
int c[100010];
int main() {
fast;
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> t[i] >> l[i] >> r[i] >> c[i];
}
ll ans = INF;
for(int i=0; i<(1<<m); i++) {
vector<int> v;
vector<pii> I;
ll cost = 0;
for(int j=0; j<m; j++) {
if(i & (1<<j)) {
cost += c[j];
v.eb(j);
}
}
sort(all(v), [&] (int i, int j) {
return t[i] < t[j];
});
int T = 0;
for(auto j : v) {
vector<pii> J;
for(auto k : I) {
if(k.fi > 1) k.fi += t[j] - T;
if(k.se < n) k.se -= t[j] - T;
if(k.fi <= k.se) J.eb(k);
}
J.eb(l[j], r[j]);
sort(all(J));
I.clear();
for(auto k : J) {
if(I.size() && k.fi <= I.back().se + 1) I.back().se = max(I.back().se, k.se);
else I.eb(k);
}
T = t[j];
}
if(I == vector<pii> {mp(1, n)}) ans = min(ans, cost);
}
if(ans == INF) cout << -1;
else cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
105 ms |
396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
384 KB |
Output is correct |
| 4 |
Correct |
79 ms |
400 KB |
Output is correct |
| 5 |
Correct |
91 ms |
384 KB |
Output is correct |
| 6 |
Correct |
100 ms |
384 KB |
Output is correct |
| 7 |
Correct |
105 ms |
400 KB |
Output is correct |
| 8 |
Correct |
125 ms |
384 KB |
Output is correct |
| 9 |
Correct |
113 ms |
384 KB |
Output is correct |
| 10 |
Correct |
113 ms |
384 KB |
Output is correct |
| 11 |
Correct |
161 ms |
384 KB |
Output is correct |
| 12 |
Correct |
93 ms |
384 KB |
Output is correct |
| 13 |
Correct |
100 ms |
384 KB |
Output is correct |
| 14 |
Correct |
92 ms |
384 KB |
Output is correct |
| 15 |
Correct |
97 ms |
396 KB |
Output is correct |
| 16 |
Correct |
121 ms |
384 KB |
Output is correct |
| 17 |
Correct |
133 ms |
384 KB |
Output is correct |
| 18 |
Correct |
104 ms |
384 KB |
Output is correct |
| 19 |
Correct |
129 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
105 ms |
396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
384 KB |
Output is correct |
| 4 |
Correct |
79 ms |
400 KB |
Output is correct |
| 5 |
Correct |
91 ms |
384 KB |
Output is correct |
| 6 |
Correct |
100 ms |
384 KB |
Output is correct |
| 7 |
Correct |
105 ms |
400 KB |
Output is correct |
| 8 |
Correct |
125 ms |
384 KB |
Output is correct |
| 9 |
Correct |
113 ms |
384 KB |
Output is correct |
| 10 |
Correct |
113 ms |
384 KB |
Output is correct |
| 11 |
Correct |
161 ms |
384 KB |
Output is correct |
| 12 |
Correct |
93 ms |
384 KB |
Output is correct |
| 13 |
Correct |
100 ms |
384 KB |
Output is correct |
| 14 |
Correct |
92 ms |
384 KB |
Output is correct |
| 15 |
Correct |
97 ms |
396 KB |
Output is correct |
| 16 |
Correct |
121 ms |
384 KB |
Output is correct |
| 17 |
Correct |
133 ms |
384 KB |
Output is correct |
| 18 |
Correct |
104 ms |
384 KB |
Output is correct |
| 19 |
Correct |
129 ms |
384 KB |
Output is correct |
| 20 |
Incorrect |
58 ms |
512 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
