oj.uz

Submission #85666

# Submission time Handle Problem Language Result Execution time Memory
85666 2018-11-21T10:28:10 Z chunghan 매트 (KOI15_mat) C++17
44 / 100
 694 ms 117892 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++) {
    for(int j = 0; j < 2*N; j++) {
      if(L[j].P && L[j].K != -1)
        solve(j, i);
      if(!L[i].P && L[i].K != -1)
        solve(i, j);
    }
  }
  cout << rst;
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 532 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 532 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 652 KB Output is correct
2 Correct 2 ms 652 KB Output is correct
3 Incorrect 2 ms 696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1860 KB Output is correct
2 Correct 5 ms 1864 KB Output is correct
3 Correct 5 ms 1864 KB Output is correct
4 Correct 5 ms 1876 KB Output is correct
5 Correct 5 ms 1916 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 105944 KB Output is correct
2 Correct 333 ms 105944 KB Output is correct
3 Correct 315 ms 106352 KB Output is correct
4 Correct 298 ms 106368 KB Output is correct
5 Correct 326 ms 115640 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 117892 KB Output is correct
2 Correct 694 ms 117892 KB Output is correct
3 Correct 670 ms 117892 KB Output is correct
4 Correct 676 ms 117892 KB Output is correct
5 Correct 680 ms 117892 KB Output is correct
6 Correct 555 ms 117892 KB Output is correct
7 Incorrect 684 ms 117892 KB Output isn't correct
8 Halted 0 ms 0 KB -