oj.uz

Submission #18034

# Submission time Handle Problem Language Result Execution time Memory
18034 2016-01-18T13:26:19 Z ainta 매트 (KOI15_mat) C++
100 / 100
 211 ms 72180 KB 
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int n, D[3010][6010], DD[6010], W;
vector<int>E[6010];
struct A{
    int b, e, H, ck, g;
    bool operator<(const A &p)const{
        return e<p.e;
    }
}w[3010];
struct X{
    int x, num;
    bool operator<(const X &p)const{
        return x<p.x;
    }
}ord[10100];
int main(){
    int i, j, k, cnt = 0, x;
    scanf("%d%d",&n,&W);
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d%d",&w[i].ck,&w[i].b,&w[i].e,&w[i].H,&w[i].g);
        ord[i].x = w[i].b, ord[i].num = i;
        ord[i+n].x = w[i].e, ord[i+n].num = i+n;
    }
    sort(ord+1,ord+n+n+1);
    for(i=1;i<=n+n;i++){
        if(i == 1 || ord[i].x != ord[i-1].x)cnt++;
        if(ord[i].num <= n)w[ord[i].num].b = cnt;
        else w[ord[i].num - n].e = cnt;
    }
    sort(w+1,w+n+1);
    for(i=1;i<=n;i++)E[w[i].b].push_back(i);
    for(i=1;i<=n;i++){
        for(j=1;j<w[i].b;j++)DD[w[i].b]=max(DD[w[i].b],DD[j]);
        D[i][w[i].b] = max(D[i][w[i].b], DD[w[i].b] + w[i].g);
        D[i][1] = max(D[i][1], w[i].g);
        for(j=1;j<w[i].e;j++){
            for(k=0;k<E[j].size();k++){
                x = E[j][k];
                if(w[i].ck == w[x].ck)continue;
                if(w[i].H + w[x].H > W)continue;
                if(w[x].e <= w[i].e) D[i][w[x].e] = max(D[i][w[x].e], D[i][j] + w[x].g);
                else D[x][w[i].e] = max(D[x][w[i].e], D[i][j] + w[x].g);
            }
            D[i][j+1] = max(D[i][j],D[i][j+1]);
        }
        DD[w[i].e] = max(DD[w[i].e], D[i][w[i].e]);
    }
    for(i=1;i<=cnt;i++)DD[i]=max(DD[i],DD[i-1]);
    printf("%d\n",DD[cnt]);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 72180 KB Output is correct
2 Correct 108 ms 72180 KB Output is correct
3 Correct 92 ms 72180 KB Output is correct
4 Correct 107 ms 72180 KB Output is correct
5 Correct 19 ms 72180 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 72180 KB Output is correct
2 Correct 209 ms 72180 KB Output is correct
3 Correct 211 ms 72180 KB Output is correct
4 Correct 206 ms 72180 KB Output is correct
5 Correct 140 ms 72180 KB Output is correct
6 Correct 86 ms 72180 KB Output is correct
7 Correct 170 ms 72180 KB Output is correct
8 Correct 80 ms 72180 KB Output is correct
9 Correct 36 ms 72180 KB Output is correct
10 Correct 86 ms 72180 KB Output is correct