oj.uz

Submission #85679

# Submission time Handle Problem Language Result Execution time Memory
85679 2018-11-21T10:49:43 Z chunghan 매트 (KOI15_mat) C++17
44 / 100
 605 ms 63908 KB 
#include<bits/stdc++.h>

typedef long long int lld;

using namespace std;

class Line {
  public:
    int P, X, I, H, left, K;
    Line(int P, int X, int I, int H, int 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;
int 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;
  int 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, 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 < L.size(); i++) {
    if(L[i].K == -1) id[L[i].I] = i;
    else L[i].left = id[L[i].I];
  }

  for(int i = 0; i < L.size(); i++) {
    for(int j = 0; j < L.size(); 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;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < L.size(); i++) {
                  ~~^~~~~~~~~~
mat.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < L.size(); i++) {
                  ~~^~~~~~~~~~
mat.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < L.size(); j++) {
                    ~~^~~~~~~~~~

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 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 652 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 652 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 4 ms 1640 KB Output is correct
2 Correct 4 ms 1640 KB Output is correct
3 Correct 4 ms 1640 KB Output is correct
4 Correct 4 ms 1644 KB Output is correct
5 Correct 5 ms 1656 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 57920 KB Output is correct
2 Correct 267 ms 57920 KB Output is correct
3 Correct 262 ms 58248 KB Output is correct
4 Correct 278 ms 58368 KB Output is correct
5 Correct 272 ms 62396 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 63908 KB Output is correct
2 Correct 580 ms 63908 KB Output is correct
3 Correct 590 ms 63908 KB Output is correct
4 Correct 583 ms 63908 KB Output is correct
5 Correct 605 ms 63908 KB Output is correct
6 Correct 433 ms 63908 KB Output is correct
7 Incorrect 579 ms 63908 KB Output isn't correct
8 Halted 0 ms 0 KB -