Submission #1163621
Source Code Expand
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <complex>
#include <cctype>
#include <cassert>
#include <sstream>
#include <ctime>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;
typedef vector<pii> vp;
#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
const ll MOD = 1000000007ll;
int W, H, Q;
vector<pii> B[2]; // tate, yoko
void insert(set<pii> &s, int x) {
if (s.empty()) return;
set<pii>::iterator it = s.lower_bound(pii(x, x));
if (it == s.end() || it->first > x) it--;
pii n1 = *it, n2 = *it;
n1.second = x - 1; n2.first = x + 1;
s.erase(*it);
if (n1.second >= n1.first) s.insert(n1);
if (n2.second >= n2.first) s.insert(n2);
}
int nextfind(set<pii> &s, int x, bool rev) {
set<pii>::iterator it = s.lower_bound(pii(x, x));
int res = INF;
if (rev) res = -INF;
if (it == s.end() || rev) it--;
if (!rev) {
if (it->first <= x && it->second >= x) chmin(res, x);
if (it->first >= x) chmin(res, it->first);
if (it != s.begin()) {
it--;
if (it->second >= x) chmin(res, it->second);
}
}
else {
if (it->first <= x && it->second >= x) res = x;
else if (it->second <= x) chmax(res, it->second);
}
return res;
}
void update(map<int, ll> &m, int pos, ll x) {
if (m.find(pos) == m.end()) m[pos] = x;
else chmin(m[pos], x);
}
int main() {
cin >> W >> H >> Q;
REP(i, Q) {
int t, d, x;
scanf("%d %d %d", &t, &d, &x);
B[d].push_back(pii(t, x));
}
assert(W <= 100);
assert(H <= 100);
ll ans = INFL;
bool ng = false;
FOR(x, 1, W + 1) FOR(y, 1, H + 1) {
ll sum = 0;
REP(i, 2) {
priority_queue<pii, vector<pii>, greater<pii> > pq;
REP(j, B[i].size()) pq.push(B[i][j]);
vector<set<pii> > vs;
while (!pq.empty()) {
set<pii> s;
if (i == 0) s.insert(pii(1, W));
else s.insert(pii(1, H));
int nt = pq.top().first;
while (!pq.empty()) {
pii now = pq.top();
if (now.first != nt) break;
pq.pop();
insert(s, now.second);
}
if (s.size() == 0) {
ng = true;
break;
}
vs.push_back(s);
}
if (ng) break;
map<int, ll> pos;
if (i == 0) pos[x] = 0;
else pos[y] = 0;
REP(j, vs.size()) {
map<int, ll> nextpos;
for (map<int, ll>::iterator it = pos.begin(); it != pos.end(); it++) {
int now = it->first;
int ncost = it->second;
int next = nextfind(vs[j], now, false);
if (next != INF) update(nextpos, next, ncost + abs(next - now));
if (next == it->first) continue;
next = nextfind(vs[j], now, true);
if (next != -INF) update(nextpos, next, ncost + abs(next - now));
}
pos = nextpos;
}
ll now = INFL;
for (map<int, ll>::iterator it = pos.begin(); it != pos.end(); it++)
chmin(now, it->second);
sum += now;
}
chmin(ans, sum);
}
if (ng) puts("-1");
else cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ビーム |
User |
tkmst201 |
Language |
C++ (GCC 5.4.1) |
Score |
30 |
Code Size |
3646 Byte |
Status |
RE |
Exec Time |
2104 ms |
Memory |
10768 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:93:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &t, &d, &x);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
0 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt |
Subtask2 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
1 ms |
256 KB |
subtask1_06.txt |
AC |
9 ms |
256 KB |
subtask1_07.txt |
AC |
39 ms |
256 KB |
subtask1_08.txt |
AC |
8 ms |
256 KB |
subtask1_09.txt |
AC |
71 ms |
256 KB |
subtask1_10.txt |
AC |
1335 ms |
256 KB |
subtask1_11.txt |
AC |
7 ms |
256 KB |
subtask1_12.txt |
AC |
2 ms |
256 KB |
subtask1_13.txt |
AC |
1 ms |
256 KB |
subtask1_14.txt |
AC |
1 ms |
256 KB |
subtask1_15.txt |
AC |
6 ms |
256 KB |
subtask1_16.txt |
AC |
97 ms |
256 KB |
subtask1_17.txt |
AC |
166 ms |
256 KB |
subtask1_18.txt |
AC |
1 ms |
256 KB |
subtask1_19.txt |
AC |
1 ms |
256 KB |
subtask1_20.txt |
AC |
4 ms |
256 KB |
subtask1_21.txt |
AC |
1398 ms |
256 KB |
subtask1_22.txt |
AC |
3 ms |
256 KB |
subtask1_23.txt |
AC |
2 ms |
256 KB |
subtask1_24.txt |
AC |
1 ms |
256 KB |
subtask1_25.txt |
AC |
1 ms |
256 KB |
subtask1_26.txt |
AC |
1 ms |
256 KB |
subtask1_27.txt |
AC |
20 ms |
256 KB |
subtask1_28.txt |
AC |
1 ms |
256 KB |
subtask1_29.txt |
AC |
948 ms |
256 KB |
subtask1_30.txt |
AC |
291 ms |
256 KB |
subtask2_01.txt |
RE |
118 ms |
1180 KB |
subtask2_02.txt |
RE |
118 ms |
1208 KB |
subtask2_03.txt |
AC |
208 ms |
9052 KB |
subtask2_04.txt |
RE |
117 ms |
1528 KB |
subtask2_05.txt |
RE |
117 ms |
1276 KB |
subtask2_06.txt |
RE |
119 ms |
1104 KB |
subtask2_07.txt |
RE |
118 ms |
1164 KB |
subtask2_08.txt |
TLE |
2103 ms |
2208 KB |
subtask2_09.txt |
TLE |
2103 ms |
2228 KB |
subtask2_10.txt |
RE |
116 ms |
1104 KB |
subtask2_11.txt |
RE |
116 ms |
1400 KB |
subtask2_12.txt |
RE |
117 ms |
1104 KB |
subtask2_13.txt |
TLE |
2104 ms |
10768 KB |
subtask2_14.txt |
RE |
116 ms |
1276 KB |
subtask2_15.txt |
RE |
96 ms |
256 KB |
subtask2_16.txt |
RE |
97 ms |
256 KB |
subtask2_17.txt |
RE |
117 ms |
1276 KB |
subtask2_18.txt |
RE |
118 ms |
1228 KB |
subtask2_19.txt |
RE |
118 ms |
1400 KB |
subtask2_20.txt |
RE |
117 ms |
1276 KB |
subtask2_21.txt |
AC |
320 ms |
5072 KB |
subtask2_22.txt |
AC |
535 ms |
3912 KB |
subtask2_23.txt |
AC |
210 ms |
8544 KB |
subtask2_24.txt |
TLE |
2103 ms |
2412 KB |
subtask2_25.txt |
RE |
117 ms |
1156 KB |
subtask2_26.txt |
RE |
115 ms |
1124 KB |
subtask2_27.txt |
RE |
117 ms |
1208 KB |
subtask2_28.txt |
RE |
117 ms |
1400 KB |
subtask2_29.txt |
RE |
118 ms |
1224 KB |
subtask2_30.txt |
AC |
958 ms |
3100 KB |