結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 Fu_L
|
| 提出日時 | 2023-04-29 17:18:22 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,891 bytes |
| コンパイル時間 | 2,198 ms |
| コンパイル使用メモリ | 202,076 KB |
| 実行使用メモリ | 25,888 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-29 17:18:31 |
| 合計ジャッジ時間 | 9,240 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define rrep(i, a, b) for(ll i = a; i >= b; i--)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int m = 14;
int n, t;
int a[3000], b[3000], c[3000], d[3000];
int dist[200][200];
int ndist[200][200];
int mdist[200][200];
int curx = -1, cury = -1;
ll cnt = 0;
ll money = 1000000;
int main(void) {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> t;
rep(i, 0, n) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
a[i]--;
b[i]--;
c[i]--;
d[i]--;
}
rep(i, 0, m * m) {
rep(j, 0, m * m) {
dist[i][j] = 100000000;
}
}
rep(i, 0, m * m) {
rep(j, 0, m * m) {
if(i == j) {
dist[i][j] = 0;
} else if(abs(i - j) == 1 or abs(i - j) == m) {
dist[i][j] = 1000;
}
}
}
rep(k, 0, m * m) {
rep(i, 0, m * m) {
rep(j, 0, m * m) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
rep(day, 0, t) {
ll u, v;
cin >> u >> v;
assert(u == money);
if(u == -1 and v == -1) {
return 0;
}
if(day <= 23) {
cout << 2 << endl;
money += 60 * cnt;
continue;
}
if(money < 2000000) {
cout << 3 << endl;
money += 50000;
money += 60 * cnt;
continue;
}
if(curx == -1 and cury == -1) {
curx = rand() % m, cury = rand() % m;
}
ll ma = 0;
int mx = -1, my = -1, mz = -1, mw = -1;
rep(dir, 0, 4) {
int nx = curx, ny = cury, nz = nx + dx[dir], nw = ny + dy[dir];
if(nz < 0 or m <= nz or nw < 0 or m <= nw) continue;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
ndist[i][j] = dist[i][j];
}
}
ndist[nx * m + ny][nz * m + nw] = 223;
ndist[nz * m + nw][nx * m + ny] = 223;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
ndist[i][j] = min(ndist[i][j], ndist[i][nx * m + ny] + ndist[nx * m + ny][nz * m + nw] + ndist[nz * m + nw][j]);
ndist[i][j] = min(ndist[i][j], ndist[i][nz * m + nw] + ndist[nz * m + nw][nx * m + ny] + ndist[nx * m + ny][j]);
}
}
ll sum = 0;
rep(i, 0, n) {
int ti = ndist[a[i] * m + b[i]][c[i] * m + d[i]];
rep(j, 0, 1000) {
if((ti - 223 * j) % 1000 == 0) {
sum += j;
break;
}
}
}
if(sum > ma) {
ma = sum;
mx = nx;
my = ny;
mz = nz;
mw = nw;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
mdist[i][j] = ndist[i][j];
}
}
}
}
// cout << ma << " " << cnt << endl;
if(60ll * (ma - cnt) * (t - day) >= 2000000) {
cout << 1 << ' ' << mx + 1 << ' ' << my + 1 << ' ' << mz + 1 << ' ' << mw + 1 << endl;
curx = mz;
cury = mw;
rep(i, 0, m * m) {
rep(j, 0, m * m) {
dist[i][j] = mdist[i][j];
}
}
cnt = ma;
money -= 2000000;
money += 60 * cnt;
} else {
curx = -1;
cury = -1;
cout << 3 << endl;
money += 50000;
money += 60 * cnt;
}
// cout << day << " " << cnt << " " << money<< endl;
}
}