oj.uz

답안 #445914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445914 2021-07-20T07:36:25 Z kig9981 치료 계획 (JOI20_treatment) C++17
0 / 100
 3000 ms 2492 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const long long INF=0x3f3f3f3f3f3f3f3fLL;
vector<tuple<int,int,int,int,int>> A;
vector<int> adj[5000];
int chk[5000];
long long dist[5000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	priority_queue<pair<long long,int>> Q;
	long long ans;
	cin>>N>>M; A.resize(M);
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(l--==1) chk[i]|=1;
		if(r==N) chk[i]|=2;
		tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
		for(int j=0;j<i;j++) {
			auto[x1,y1,x2,y2,t]=A[j];
			if(max(x1,t)<=min(x2,r) && max(y1,l)<=min(y2,aa)) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	for(int i=0;i<M;i++) if(chk[i]&1) Q.emplace(-(dist[i]=get<4>(A[i])),i);
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		for(auto n: adj[c]) if(dist[n]==INF && dist[n]>dist[c]+get<4>(A[n])) {
			dist[n]=dist[c]+get<4>(A[n]);
			Q.emplace(-dist[n],n);
		}
	}
	ans=INF;
	for(int i=0;i<M;i++) if(chk[i]&2) ans=min(ans,dist[i]);
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3077 ms 2492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 460 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 460 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3077 ms 2492 KB Time limit exceeded
2 Halted 0 ms 0 KB -