結果

問題 No.614 壊れたキャンパス
ユーザー wajima_wataruwajima_wataru
提出日時 2017-12-28 16:18:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 1,880 bytes
コンパイル時間 937 ms
コンパイル使用メモリ 92,968 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-12-21 09:01:01
合計ジャッジ時間 4,316 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 158 ms
8,564 KB
testcase_09 AC 238 ms
12,912 KB
testcase_10 AC 251 ms
13,020 KB
testcase_11 AC 168 ms
8,064 KB
testcase_12 AC 233 ms
8,192 KB
testcase_13 AC 177 ms
8,192 KB
testcase_14 AC 180 ms
8,556 KB
testcase_15 AC 168 ms
10,624 KB
testcase_16 AC 166 ms
9,728 KB
testcase_17 AC 223 ms
14,208 KB
testcase_18 AC 144 ms
9,452 KB
testcase_19 AC 147 ms
9,456 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

#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