結果

問題 No.614 壊れたキャンパス
コンテスト
ユーザー wajima_wataru
提出日時 2017-12-28 16:18:09
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 1,880 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 937 ms
コンパイル使用メモリ 92,968 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-12-21 09:01:01
合計ジャッジ時間 4,316 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:42:25: warning: narrowing conversion of 'S' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   42 |         Prev prev = {0, S, 0};
      |                         ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include <climits>
#include <functional>
#include "math.h"
using namespace std;
typedef long long ll;

struct P {
	bool operator<(const P& p) const {
        return b < p.b;
    }
    int b, c;
    ll val;
};

struct Prev {
	bool operator<(const Prev& p) const {
        return c < p.c;
    }
	int b, c;
	ll val;
};

int main() {
	ll MAX = LLONG_MAX / 2;
    ll N, M, K, S, T;
    cin >> N >> M >> K >> S >> T;
    vector<vector<P> > R(N - 1, vector<P>());
    for (int i = 0; i < M; ++i) {
    	P p;
    	int a;
		cin >> a >> p.b >> p.c;
		p.val = MAX;
		R[a - 1].push_back(p);
	}

	vector<Prev> prevs = vector<Prev>();
	Prev prev = {0, S, 0};
	prevs.push_back(prev);
    for (int i = 0; i < N - 1; ++i) {
    	sort(R[i].begin(), R[i].end());
    	int k_max = prevs.size() - 1;
    	int k = 0;
    	ll min_val = MAX;
        for (int j = 0; j < R[i].size(); ++j) {
        	while (k <= k_max && prevs[k].c <= R[i][j].b) {
				min_val = min(min_val, prevs[k].val - prevs[k].c);
				k++;
        	}
        	R[i][j].val = min(R[i][j].val, min_val + R[i][j].b);
        }
        k = k_max;
        min_val = MAX;
        for (int j = R[i].size() - 1; j >= 0; --j) {
        	while (k >= 0 && prevs[k].c >= R[i][j].b) {
				min_val = min(min_val, prevs[k].val + prevs[k].c);
				k--;
        	}
        	R[i][j].val = min(R[i][j].val, min_val - R[i][j].b);
        }
        prevs.clear();
        for (int j = 0; j < R[i].size(); ++j) {
        	Prev prev = {R[i][j].b, R[i][j].c, R[i][j].val};
        	prevs.push_back(prev);
		}
		sort(prevs.begin(), prevs.end());
	}
	ll ans = MAX;
    for (int j = 0; j < prevs.size(); ++j) {
    	ans = min(ans, abs(prevs[j].c - T) + prevs[j].val);
    }
    if (ans < MAX) {
    	cout << ans << endl;
    } else {
    	cout << -1 << endl;
    }
}
0