Submission #1031949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031949		gs25	요리 강좌 (KOI17_cook)	C++17	100 / 100	455 ms	163124 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 < y.first; 
    }); 
    for(int i=1; i<=n; i++){
      if(v.empty()){
        dp2[i][t] = inf; 
      }
      else{
        for(int k=0; k<3; k++){
          if(v[k].second != i && v[k].second != f[i]){
            //if(i==1 && t==2) cerr << v[k].first << "fuckkkkkkkkkkkkkkkkk" << endl; 
            dp2[i][t] = v[k].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}); 
      }
      //cerr << i << " " << dp[i][t] << " " << dp1[i][t] << endl;
    }
  } 
  ll ans = inf; 
  for(int i=1; i<=n; i++) ans = min(dp[i][m],ans); 
  cout << ans; 
}

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