結果

問題 No.2366 登校
ユーザー t98slidert98slider
提出日時 2023-06-30 22:45:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,416 bytes
コンパイル時間 1,676 ms
コンパイル使用メモリ 171,220 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-07 22:00:00
合計ジャッジ時間 2,069 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T> istream& operator >> (istream& is, vector<T>& vec) {
for(T& x : vec) is >> x;
return is;
}
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) {
if(vec.empty()) return os;
os << vec[0];
for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it;
return os;
}
/*int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int h, w, k, t;
cin >> h >> w >> k >> t;
if(t >= h + w){
cout << 0 << '\n';
return 0;
}
vector<vector<ll>> C(h, vector<ll>(w)), D(h, vector<ll>(w));
for(int i = 0; i < k; i++){
int y, x, v1, v2;
cin >> y >> x >> v1 >> v2;
y--, x--;
C[y][x] = v1;
D[y][x] = v2;
}
const ll INF = 1ll << 60;
//, y, x
vector<vector<vector<ll>>> dptb(h + w, vector<vector<ll>>(h, vector<ll>(w, INF)));
vector<rpriority_queue<tuple<ll, int, int>>> pqtb(h + w);
dptb[0][0][0] = 0;
pqtb[0].emplace(0, 0, 0);
ll ans = INF;
for(int hv = 0; hv < h + w; hv++){
auto &pq = pqtb[hv];
auto &dp = dptb[hv];
while(!pq.empty()){
ll d;
int y, x;
tie(d, y, x) = pq.top();
pq.pop();
if(d > dp[y][x]) continue;
if(C[y][x] && hv + D[y][x] < h + w){
int hv2 = hv + D[y][x];
if(d - C[y][x] + 1 <= dptb[hv2][y][x]){
dptb[hv2][y][x] = d - C[y][x] + 1;
pqtb[hv2].emplace(dptb[hv2][y][x], y, x);
}
}
for(int i = 0; i < 4; i++){
int ny = y + (i == 0) - (i == 1);
int nx = x + (i == 2) - (i == 3);
if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
if(d + 1 >= dp[ny][nx]) continue;
dp[ny][nx] = d + 1;
pq.emplace(d + 1, ny, nx);
}
}
for(int y = 0; y < h; y++){
cerr << dp[y] << '\n';
}
cerr << '\n';
if(dp[h - 1][w - 1] <= t){
cout << hv << '\n';
return 0;
}
}
cout << -1 << '\n';
}*/
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int h, w, k, t;
cin >> h >> w >> k >> t;
if(t >= h + w - 2){
cout << 0 << '\n';
return 0;
}
vector<vector<ll>> C(h, vector<ll>(w)), D(h, vector<ll>(w));
for(int i = 0; i < k; i++){
int y, x, v1, v2;
cin >> y >> x >> v1 >> v2;
y--, x--;
C[y][x] = v1;
D[y][x] = v2;
}
const ll INF = 1ll << 60;
//, y, x
ll ng = 0, ok = INF, mid;
while(ng + 1 < ok){
mid = (ng + ok) / 2;
bool flag = false;
for(int y = 0; y < h && !flag; y++){
for(int x = 0; x < w; x++){
if(C[y][x] >= 1){
ll k = mid / D[y][x];
ll tim = h + w - 2;
tim += k;
tim -= C[y][x] * k;
if(tim <= t){
flag = true;
break;
}
}
}
}
(flag ? ok : ng) = mid;
}
if(ok == INF) ok = -1;
cout << ok << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0