2014年12月14日 星期日

2014/12/14 ACM-ICPC Live Archive 3983 - Robotruck

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1984 */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

typedef pair<int, int> iv;
#define i first
#define v second

int T;
int C, N;

int x[200000], y[200000];

int w[200000];
int pre_w[200000];

int path[200000];

deque<iv> deq;

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &C);

        scanf("%d", &N);

        pre_w[0] = 0;
        path[0] = 0;
        w[0] = x[0] = y[0] = 0;

        for(int Ni = 1; Ni <= N; Ni++)
        {
            scanf("%d %d %d", &x[Ni], &y[Ni], &w[Ni]);
            pre_w[Ni] = pre_w[Ni-1]+w[Ni];
            path[Ni] = path[Ni-1]+abs(x[Ni]-x[Ni-1])+abs(y[Ni]-y[Ni-1]);
        }

        while( !deq.empty() ) deq.pop_back();
        deq.push_back(iv(0, 0) );

        for(int Ni = 1; Ni <= N; Ni++)
        {
            while( pre_w[Ni]-pre_w[deq.front().i] > C ) deq.pop_front();

            int v = path[Ni]+deq.front().v+x[Ni]+y[Ni];
            int p = v+x[Ni+1]+y[Ni+1]-path[Ni+1];

            while( !deq.empty() && deq.back().v >= p ) deq.pop_back();
            deq.push_back(iv(Ni, p) );

            if( Ni == N )
                printf("%d\n", v);
         }

         if( T ) puts("");
    }
}

沒有留言:

張貼留言