Submission #1031837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031837		gs25	요리 강좌 (KOI17_cook)	C++17	0 / 100	3 ms	5208 KiB

cook

#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std; 

const int MAXN = 3010; 
typedef long long ll; 

ll dp[MAXN][MAXN], dp1[MAXN][MAXN], dp2[MAXN][MAXN]; 
ll T; 
ll psum[MAXN][MAXN]; 
int f[MAXN]; 
const ll inf = 1e18; 

int main(void){
  ios::sync_with_stdio(false); cin.tie(nullptr); 
  int n,m; cin >> n >> m; 
  int s,e; cin >> s >> e; 
  cin >> T; 
  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      int x; cin >> x; psum[i][j] = psum[i][j-1] + x; 
    }
  }
  for(int i=1; i<=n; i++) cin >> f[i]; 
  for(int i=1; i<=n; i++) dp1[i][0] = -T; 
  deque<pair<ll,int>> dq[MAXN]; 
  deque<pair<ll,int>> dq1[MAXN]; 
  for(int i=1; i<=n; i++){
    dq[i].push_back({-T,0});
    if(s==1) dq1[i].push_back({-T,0}); 
    dp2[i][0] = -T; 
  }
  for(int t=1; t<=m; t++){
    vector<pair<ll,int>> v; 
    for(int i=1; i<=n; i++){
      while(!dq[i].empty() && dq[i].front().second < max(t-e,0)) dq[i].pop_front(); 
      while(!dq1[i].empty() && dq1[i].front().second < max(t-e,0)) dq1[i].pop_front(); 
      dp[i][t] = T + psum[i][t] + dq[i].front().first;  
      if(!dq1[i].empty()) dp1[i][t] = T + psum[i][t] + dq1[i].front().first, v.push_back({dp1[i][t],i}); 
      else dp1[i][t] = inf; 
    }
    sort(all(v),[](auto & x, auto & y){
      return x.first < x.second; 
    }); 
    for(int i=1; i<=n; i++){
      if(v.empty()){
        dp2[i][t] = inf; 
      }
      else{
        for(int k=0; k<3; k++){
          if(v[0].second != i && v[0].second != f[i]){
            dp2[i][t] = v[0].first - psum[i][t]; break; 
          }
        }
      }
      while(!dq[i].empty() && dq[i].back().first >= dp2[i][t]) dq[i].pop_back(); 
      dq[i].push_back({dp2[i][t],t}); 
      if(t>=s-1) {
        while(!dq1[i].empty() && dq1[i].back().first >= dp2[i][t-s+1]) dq1[i].pop_back(); 
        //cerr << "wtf?? " << i << " " << t << " " << dp2[i][t-s+1] << endl;
        dq1[i].push_back({dp2[i][t-s+1],t-s+1}); 
      }
    }
  }
  ll ans = inf; 
  for(int i=1; i<=n; i++) ans = min(dp[i][m],ans); 
  cout << ans; 
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 44