Submission #159567

#	Time	Username	Problem	Language	Result	Execution time	Memory
159567		geon040702	장애물 경기 (KOI16_dd)	C++14	100 / 100	145 ms	12920 KiB

dd

#include <bits/stdc++.h>
#define MAX 999999999
using namespace std;

struct Item
{
    int x, y[2];
    bool operator<(const Item &r) const {
        return x < r.x;
    }
};

int n, start_y, end_x;
Item hurdle[100010];

set< pair<int,int> > data1;
int data2[100010];

void calc_route()
{
    int i, j, temp[2];
    int ans = MAX, cnt = 0;

    set< pair<int, int> >::iterator pos, st, ed;

    data1.insert(make_pair(start_y, 0));
    for(i = 1 ; i <= n ; i++)
    {
        temp[0] = temp[1] = MAX;
        st = data1.lower_bound(make_pair(hurdle[i].y[0], 0));
        ed = data1.upper_bound(make_pair(hurdle[i].y[1], MAX));
        for(pos = st; pos != ed ; ++pos)
            for(j = 0 ; j <= 1 ; j++)
                temp[j] = min(temp[j], (*pos).second + abs(hurdle[i].y[j] - (*pos).first));
        data1.erase(st, ed);
        for(j = 0 ; j <= 1 ; j++)
            data1.insert(make_pair(hurdle[i].y[j], temp[j]));
    }

    for(pos = data1.begin(); pos != data1.end(); ++pos)
    {
        if(ans > (*pos).second)
        {
            ans = (*pos).second;
            cnt = 0;
        }
        if(ans == (*pos).second)
            data2[cnt++] = (*pos).first;
    }
    printf("%d\n%d", ans + end_x, cnt);
    for(i = 0 ; i < cnt ; i++)
        printf(" %d", data2[i]);

}

int main(void)
{
    int i;
    scanf("%d %d %d", &n, &start_y, &end_x);

    for(i = 1 ; i <= n ; i++)
    {
        scanf("%d %d %d", &hurdle[i].x, &hurdle[i].y[0], &hurdle[i].y[1]);
    }
    sort(hurdle+1, hurdle+n+1);

    calc_route();

    return 0;
}

Compilation message (stderr)

dd.cpp: In function 'int main()':
dd.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &start_y, &end_x);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dd.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &hurdle[i].x, &hurdle[i].y[0], &hurdle[i].y[1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 36 / 36