| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584934 |
2022-06-28T07:09:56 Z |
조영욱(#8382) |
도장 모으기 (JOI14_stamps) |
C++14 |
|
1000 ms |
63724 KB |
#include <bits/stdc++.h>
using namespace std;
int n;
long long t;
long long u[3002];
long long v[3002];
long long d[3002];
long long e[3002];
const long long INF=1e15;
typedef pair<int,int> P;
typedef pair<long long,P> iP;
bool vis[54][65536];
long long dist[54][65536];
int main(void) {
scanf("%d %lld",&n,&t);
for(int i=1;i<=n;i++) {
scanf("%lld %lld %lld %lld",&u[i],&v[i],&d[i],&e[i]);
}
u[0]=INF;
v[0]=INF;
d[0]=INF;
e[0]=INF;
u[n+1]=INF;
v[n+1]=INF;
d[n+1]=INF;
e[n+1]=INF;
for(int i=0;i<3*n+6;i++) {
for(int j=0;j<65536;j++) {
dist[i][j]=INF;
vis[i][j]=false;
}
}
priority_queue<iP,vector<iP>,greater<iP>> pq;
pq.push(iP(0,P(0,0)));
dist[0][0]=0;
while (!pq.empty()) {
P now=pq.top().second;
pq.pop();
//printf("%d %d\n",now.first,now.second);
if (vis[now.first][now.second]) {
continue;
}
vis[now.first][now.second]=true;
if (now.first%3==0) {
P nt=P(now.first+1,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+u[now.first/3]) {
dist[nt.first][nt.second]=dist[now.first][now.second]+u[now.first/3];
pq.push(iP(dist[nt.first][nt.second],nt));
}
if (now.first/3!=n+1) {
nt=P(now.first+3,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+t) {
dist[nt.first][nt.second]=dist[now.first][now.second]+t;
pq.push(iP(dist[nt.first][nt.second],nt));
}
}
}
else if (now.first%3==1) {
P nt;
if (now.first/3!=0&&now.first/3!=n+1) {
nt=P(now.first,now.second|(1<<((now.first/3)-1)));
if (dist[nt.first][nt.second]>dist[now.first][now.second]) {
dist[nt.first][nt.second]=dist[now.first][now.second];
pq.push(iP(dist[nt.first][nt.second],nt));
}
}
nt=P(now.first-1,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+v[now.first/3]) {
dist[nt.first][nt.second]=dist[now.first][now.second]+v[now.first/3];
pq.push(iP(dist[nt.first][nt.second],nt));
}
nt=P(now.first+1,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+e[now.first/3]) {
dist[nt.first][nt.second]=dist[now.first][now.second]+e[now.first/3];
pq.push(iP(dist[nt.first][nt.second],nt));
}
}
else if (now.first%3==2) {
P nt=P(now.first-1,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+d[now.first/3]) {
dist[nt.first][nt.second]=dist[now.first][now.second]+d[now.first/3];
pq.push(iP(dist[nt.first][nt.second],nt));
}
if (now.first/3!=0) {
nt=P(now.first-3,now.second);
if (dist[nt.first][nt.second]>dist[now.first][now.second]+t) {
dist[nt.first][nt.second]=dist[now.first][now.second]+t;
pq.push(iP(dist[nt.first][nt.second],nt));
}
}
}
}
printf("%lld",dist[3*n+3][(1<<n)-1]);
}
Compilation message
stamps.cpp: In function 'int main()':
stamps.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d %lld",&n,&t);
| ~~~~~^~~~~~~~~~~~~~~~~
stamps.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%lld %lld %lld %lld",&u[i],&v[i],&d[i],&e[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14164 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5460 KB |
Output is correct |
| 3 |
Correct |
700 ms |
35688 KB |
Output is correct |
| 4 |
Correct |
201 ms |
29096 KB |
Output is correct |
| 5 |
Execution timed out |
1078 ms |
35668 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
63724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
63660 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
