Submission #18034

#	Time	Username	Problem	Language	Result	Execution time	Memory
18034		ainta	매트 (KOI15_mat)	C++98	100 / 100	211 ms	72180 KiB

mat

#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 / 8
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 43 / 43