結果

問題 No.3368 トッピング
コンテスト
ユーザー iro_
提出日時 2025-10-25 17:14:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,479 bytes
コンパイル時間 1,651 ms
コンパイル使用メモリ 176,780 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2025-11-17 20:32:23
合計ジャッジ時間 15,929 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 1 WA * 11 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void o(const T&, const Ts& ...)’:
main.cpp:62:36: warning: fold-expressions only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   62 |     (cout << ... << (cout << ' ', b));
      |                                    ^
main.cpp: In function ‘void in(T& ...)’:
main.cpp:78:20: warning: fold-expressions only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   78 |     (cin >> ... >> a);
      |                    ^

ソースコード

diff # 

/*＿＿＿＿＿＿
　　 ||　　　　  　|
　　 ||ACはこちらへ|
　　 ||　　　　  　|
　　 ||￣￣￣￣￣￣ 
∧_∧||
(`･ω･||
（ つ||０
　uｰu*/
#include <bits/stdc++.h>
using namespace std;
//output and debug
template <class T> using V = vector<T>;
template <class T, class U> 
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}
template <class T> ostream& operator<<(ostream& os,const V<T>& v) {
    os << "[";
    bool f = false;
    for (auto d : v) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "]";
}
template <class T> ostream& operator<<(ostream& os,const set<T>& s) {
    os << "{";
    bool f = false;
    for (auto d : s) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "}";
}
template <class T> ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{";
    bool f = false;
    for (auto d : s) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "}";
}
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& s) {
    os << "{";
    bool f = false;
    for (auto p : s) {
        if (f) os << ", ";
        f = true;
        os << p.first << ": " << p.second;
    }
    return os << "}";
}
template<class T, class... Ts>
void o(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}
#ifdef LOCAL
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        o(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif
// input
template<class... T>
void in(T&... a){
    (cin >> ... >> a);
}
template<class T> void in(vector<T>& a){ for(auto&& i : a) in(i); }
template<class T, class L> void in(pair<T, L>& p){ in(p.first); in(p.second); }
template<class T> void in(T& a){ cin >> a; }

#define rep1(n)          for(ll i = 0; i < n; ++i)
#define rep2(i, n)       for(ll i = 0; i < n; ++i)
#define rep3(i, j, n)    for(ll i = j; i < n; ++i)
#define overload3(a, b, c,  e, ...) e
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i,n) for(ll i = n-1;i>=0;--i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using ll = long long ;
using ld = long double;
using pa = pair<ll,ll>;
using t2 = tuple<ll,ll>;
using tu = tuple<ll,ll,ll>;
using vi = vector<ll>;
using vs = vector<string>;
using vp = vector<pa>;
using vvi = vector<vi>;
using vvp = vector<vp>;
using vvvi = vector<vvi>;
using v4 = vector<vvvi>;
using vt = vector<tu>;
const ll INF = (1ll << 29);
const ll inf = INF*INF;
const int dh[4]={1,-1,0,0};
const int dw[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
const int dx[4]={0,0,1,-1};
const string mv = "DURL";
void Yes(bool i = true){ return o(i?"Yes":"No"); }

//reversed priority_queue
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
const ll mod = 998244353;
//const ll mod = 1000000007;

int main(){
	ll n,m,c,x;
    cin >> n >> m >> c >> x;
    vector<vector<ll>> a(n,vector<ll>(m));
	rep(i,n) rep(j,m) cin >> a[i][j];
	auto up2 = [&](vector<pair<ll,ll>> &vp,ll d,ll id){
		vp.push_back(make_pair(d,id));
		sort(all(vp));
		if(vp.size()>=2) vp.pop_back();
		return;
	};
	auto chmin = [&](ll &a, ll b){
		a = min(a,b);
		return;
	};
	auto sol = [&](ll mi){
		bool flag = false;
		rep(st,m){
			if(a[0][st]<mi) continue;
			vector<vector<ll>> dp(n+1,vector<ll>(m,x+1));
			dp[0][st] = 0;
			rep(i,n-1){
				vector<pair<ll,ll>> vp;
				//o(vp);
				rep(j,m) if(dp[i][j]<= x) up2(vp,dp[i][j],j);
				//o(vp);
				rep(j,m)for(auto k:vp){
					//o(k);
					if(j == k.second && min(a[i+1][j],a[i][j])>=mi+c) chmin(dp[i+1][j],dp[i][j]+1);
					else if(j != k.second && a[i+1][j]>=mi) chmin(dp[i+1][j],dp[i][k.second]);
				}
			}
			if(min(a[0][st],a[n-1][st])<mi+c) dp[n-1][st] = x+1;
			else ++dp[n-1][st];
			rep(i,m) flag |= (dp[n-1][i]<=x); 
		}
		return flag;
	};
	auto tansaku = [&](){
    	ll ok = -1,ng = inf;
    	while(abs(ok-ng) > 1){
        	ll mid = (ok + ng)/2;
			// ll mid = l + (r-l)/2;
        	if(sol(mid)) ok = mid;
        	else ng = mid;
	  	}
		return ok;
	};
	cout << tansaku() << endl;
}
0