Submission #85663

#	Time	Username	Problem	Language	Result	Execution time	Memory
85663		chunghan	매트 (KOI15_mat)	C++11	44 / 100	648 ms	118932 KiB

mat

#include<bits/stdc++.h>

typedef long long int lld;

using namespace std;

class Line {
  public:
    int P, X, I, H, left;
    lld K;
    Line(int P, int X, int I, int H, lld K) : P(P), X(X), I(I), H(H), K(K) {}
    
    bool operator <(Line m) const{
      return this->X < m.X || (this->X == m.K && this->H > m.K);
    }
};

vector<Line> L;
lld N, W, D[3005][6005], rst = 0;

void solve(int i, int j) {
  Line r = L[i], l = L[j];

  if(l.X > r.X) return;
  lld M = 0;
  if(l.K != -1) {
    if(l.X <= L[r.left].X) {
      M = r.K + D[l.I][j];
    } else if(l.P != r.P && l.H + r.H <= W) {
      if(l.left < r.left) 
        M = r.K + D[l.I][r.left];
      else 
        M = l.K + D[r.I][l.left];
    }
  }
  M = max(r.K, M);
  if(j > 0) M = max(D[r.I][j-1], M);

  D[r.I][j] = M;
  rst = max(rst, M);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr); 
  cout.tie(nullptr);
  cin >> N >> W;
  for(int i = 0; i < N; i++) {
    int P, l, R, H;
    lld K;
    cin >> P >> l >> R >> H >> K;
    L.push_back(Line(P, l, i, H, -1));
    L.push_back(Line(P, R, i, H, K));
  }
  sort(L.begin(), L.end());
  int id[3005] = {0};
  for(int i = 0; i < 2*N; i++) {
    if(L[i].K == -1) id[L[i].I] = i;
    else L[i].left = id[L[i].I];
  }

  for(int i = 0; i < 2*N; i++) {
    if(!L[i].P && L[i].K != -1)
      for(int j = 0; j < 2*N; j++)
        solve(i, j);
    for(int j = 0; j < 2*N; j++)
      if(L[j].P && L[j].K != -1)
        solve(j, i);
  }
  cout << rst;
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 43