Submission #16852

#	Time	Username	Problem	Language	Result	Execution time	Memory
16852		hjk0553	택배 (KOI13_delivery)	C++98	100 / 100	27 ms	1208 KiB

delivery

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
int i,j,k;
int villagecount;
int volume;
int maxcarryweight=0;
int track[2001];
struct delivery
{
    int sendvillage;
    int receivevillage;
    int weight;
} data[10001];
bool compare(const delivery &a,const delivery &b)
{
    return a.receivevillage<b.receivevillage;
}
int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&villagecount,&volume);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&data[i].sendvillage,&data[i].receivevillage,&data[i].weight);
    }
    sort(data+1,data+1+n,compare);
    for(i=1;i<=n;i++)
    {
        int Max=-1e9;
        int sw=0;
        for(j=data[i].sendvillage;j<data[i].receivevillage;j++) Max=max(Max,track[j]);
        for(j=data[i].sendvillage;j<data[i].receivevillage;j++)
        {
            if(Max+data[i].weight>volume)
            {
                if(Max==0){track[j]=volume;sw=1;}
                else {track[j]+=volume-Max;sw=2;}
            }
            else track[j]+=data[i].weight;
        }
        if(sw==1) maxcarryweight+=volume;
        else if(sw==2) maxcarryweight+=volume-Max;
        else maxcarryweight+=data[i].weight;
    }
    //for(i=1;i<=villagecount;i++)
    //{
    //    printf("%d ",track[i]);
    //}
    printf("%d",maxcarryweight);
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 25 / 25