oj.uz

Submission #1031935

# Submission time Handle Problem Language Result Execution time Memory
1031935 2024-07-23T08:47:34 Z gs25 None (KOI17_cook) C++17
0 / 100
 3 ms 5208 KB 
#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[k].second != i && v[k].second != f[i]){
            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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -