oj.uz

답안 #85663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85663 2018-11-21T10:18:32 Z chunghan 매트 (KOI15_mat) C++11
44 / 100
 648 ms 118932 KB 
#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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 480 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 780 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Incorrect 2 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2308 KB Output is correct
2 Correct 4 ms 2320 KB Output is correct
3 Correct 4 ms 2348 KB Output is correct
4 Correct 4 ms 2356 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 106648 KB Output is correct
2 Correct 284 ms 106648 KB Output is correct
3 Correct 271 ms 107156 KB Output is correct
4 Correct 279 ms 107204 KB Output is correct
5 Correct 286 ms 116580 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 118932 KB Output is correct
2 Correct 620 ms 118932 KB Output is correct
3 Correct 648 ms 118932 KB Output is correct
4 Correct 639 ms 118932 KB Output is correct
5 Correct 600 ms 118932 KB Output is correct
6 Correct 473 ms 118932 KB Output is correct
7 Incorrect 633 ms 118932 KB Output isn't correct
8 Halted 0 ms 0 KB -