# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
21323 | 2017-04-13T07:39:44 Z | model_code | Cultivation (JOI17_cultivation) | C++11 | 926 ms | 49760 KB |
#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; int R,C,N; int rs[408]; int cs[408]; long long sol=999999999; long long INF; int cand_len; int cand[3999]; int uniq(int *retsu,int len) { sort(retsu, retsu+len); int nl=1; for(int i=1;i<len;i++) if(retsu[i]!=retsu[nl-1]) retsu[nl++]=retsu[i]; return nl; } int cs_uniq_len; int cs_uniq[3999]; vector<long long> qrs_tmg[3999]; vector<long long> qrs_L[3999]; vector<long long> qrs_R[3999]; vector<long long> qrs_C[3999]; void calc(int plc) { int Rnow=cand[plc]; int filled[3999]; long long max_noexist[3999]; for(int i=0;i<cs_uniq_len;i++) max_noexist[i]=INF; for(int i=0;i<N;i++) { if(Rnow>=rs[i]) for(int j=0;j<cs_uniq_len;j++) if(cs_uniq[j]==cs[i]) if(max_noexist[j]>Rnow-rs[i]-1) max_noexist[j]=Rnow-rs[i]-1; } for(int i=0;i<cs_uniq_len;i++) if(max_noexist[i]<INF){filled[i]=1;}else{filled[i]=0;} long long cur=INF; //INF 時の処理 qrs_tmg[plc].push_back(INF); int exist=0; for(int j=0;j<cs_uniq_len;j++) exist+=filled[j]; if(exist) { int next=qrs_L[plc].size(); for(int j=0;j<cs_uniq_len;j++) if(filled[j]) {qrs_L[plc].push_back(cs_uniq[j]-1);break;} for(int j=cs_uniq_len-1;j>=0;j--) if(filled[j]) {qrs_R[plc].push_back(C-cs_uniq[j]);break;} qrs_C[plc].push_back(0); int recent=qrs_L[plc][next]; for(int j=0;j<cs_uniq_len;j++) if(filled[j]) { if(qrs_C[plc][next]<cs_uniq[j]-recent-1) qrs_C[plc][next]=cs_uniq[j]-recent-1; recent=cs_uniq[j]; } } else { qrs_L[plc].push_back(INF); qrs_R[plc].push_back(INF); qrs_C[plc].push_back(INF); } //それ以外 while(cur>=0) { long long nextmax=-1; for(int j=0;j<cs_uniq_len;j++) if(max_noexist[j]<cur&&max_noexist[j]>nextmax) nextmax=max_noexist[j]; cur=nextmax; for(int j=0;j<cs_uniq_len;j++) if(max_noexist[j]==cur) filled[j]=0; //更新クエリ qrs_tmg[plc].push_back(cur); exist=0; for(int j=0;j<cs_uniq_len;j++) exist+=filled[j]; if(exist) { int next=qrs_L[plc].size(); for(int j=0;j<cs_uniq_len;j++) if(filled[j]) {qrs_L[plc].push_back(cs_uniq[j]-1);break;} for(int j=cs_uniq_len-1;j>=0;j--) if(filled[j]) {qrs_R[plc].push_back(C-cs_uniq[j]);break;} qrs_C[plc].push_back(0); int recent=qrs_L[plc][next]; for(int j=0;j<cs_uniq_len;j++) if(filled[j]) { if(qrs_C[plc][next]<cs_uniq[j]-recent-1) qrs_C[plc][next]=cs_uniq[j]-recent-1; recent=cs_uniq[j]; } } else { qrs_L[plc].push_back(INF); qrs_R[plc].push_back(INF); qrs_C[plc].push_back(INF); } } } typedef struct { long long tmg; long long L; long long R; long long C; long long from; }evs; evs event[999999]; int main() { scanf("%d%d%d",&R,&C,&N); for(int i=0;i<N;i++) scanf("%d%d",&rs[i],&cs[i]); sol*=sol; INF=sol; int cand_temp=0; for(int i=0;i<N;i++) { cs_uniq[i]=cs[i]; cand[cand_temp++]=rs[i]; if(rs[i]>1) cand[cand_temp++]=rs[i]-1; cand[cand_temp++]=rs[i]+R-1; } cs_uniq[N]=1; cs_uniq[N+1]=C; cs_uniq_len=uniq(cs_uniq,N+2); cand[cand_temp++]=1; cand[cand_temp++]=R; cand_len=uniq(cand,cand_temp); for(int i=0;i<cand_len;i++) calc(i); int events_len=0; for(int i=0;i<cand_len;i++) for(int j=0;j<qrs_tmg[i].size();j++) { event[events_len].tmg=qrs_tmg[i][j]; event[events_len].L=qrs_L[i][j]; event[events_len].R=qrs_R[i][j]; event[events_len].from=cand[i]; event[events_len++].C=qrs_C[i][j]; } sort(event, event + events_len, [](const evs &a, const evs &b) { return a.tmg > b.tmg; }); for(int looklf=0;looklf<cand_len;looklf++) { if(cand[looklf]>R) break; long long North=cand[looklf]-1; int lookrg=looklf; while(lookrg<cand_len-1) { if(cand[lookrg+1]>cand[looklf]+R-1) break; lookrg++; } long long cur_L=0; long long cur_R=0; long long cur_C=0; long long recent_tmg=INF; for(int i=0;i<events_len;i++) { if(event[i].from<cand[looklf]||event[i].from>cand[lookrg]) continue; if(recent_tmg!=event[i].tmg) { if(North>event[i].tmg+1) { if(cur_L+cur_R>cur_C) { if(sol>cur_L+cur_R+North) sol=cur_L+cur_R+North; } else { if(sol>cur_C+North) sol=cur_C+North; } } else { if(cur_L+cur_R>cur_C) { if(sol>cur_L+cur_R+event[i].tmg+1) sol=cur_L+cur_R+event[i].tmg+1; } else { if(sol>cur_C+event[i].tmg+1) sol=cur_C+event[i].tmg+1; } } } recent_tmg=event[i].tmg; if(cur_L<event[i].L) cur_L=event[i].L; if(cur_R<event[i].R) cur_R=event[i].R; if(cur_C<event[i].C) cur_C=event[i].C; } //S=0 if(cur_L+cur_R>cur_C) { if(sol>cur_L+cur_R+North) sol=cur_L+cur_R+North; } else { if(sol>cur_C+North) sol=cur_C+North; } } printf("%lld\n",sol); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40652 KB | Output is correct |
3 | Correct | 0 ms | 40652 KB | Output is correct |
4 | Correct | 0 ms | 40652 KB | Output is correct |
5 | Correct | 0 ms | 40652 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40652 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40652 KB | Output is correct |
11 | Correct | 0 ms | 40652 KB | Output is correct |
12 | Correct | 0 ms | 40652 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40652 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40652 KB | Output is correct |
3 | Correct | 0 ms | 40652 KB | Output is correct |
4 | Correct | 0 ms | 40652 KB | Output is correct |
5 | Correct | 0 ms | 40652 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40652 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40652 KB | Output is correct |
11 | Correct | 0 ms | 40652 KB | Output is correct |
12 | Correct | 0 ms | 40652 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40652 KB | Output is correct |
17 | Correct | 0 ms | 40652 KB | Output is correct |
18 | Correct | 0 ms | 40652 KB | Output is correct |
19 | Correct | 0 ms | 40652 KB | Output is correct |
20 | Correct | 0 ms | 40652 KB | Output is correct |
21 | Correct | 0 ms | 40784 KB | Output is correct |
22 | Correct | 0 ms | 40784 KB | Output is correct |
23 | Correct | 0 ms | 40652 KB | Output is correct |
24 | Correct | 0 ms | 40784 KB | Output is correct |
25 | Correct | 0 ms | 40784 KB | Output is correct |
26 | Correct | 0 ms | 40652 KB | Output is correct |
27 | Correct | 0 ms | 40784 KB | Output is correct |
28 | Correct | 0 ms | 40784 KB | Output is correct |
29 | Correct | 0 ms | 40652 KB | Output is correct |
30 | Correct | 0 ms | 40652 KB | Output is correct |
31 | Correct | 0 ms | 40784 KB | Output is correct |
32 | Correct | 0 ms | 40784 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40652 KB | Output is correct |
3 | Correct | 0 ms | 40652 KB | Output is correct |
4 | Correct | 0 ms | 40652 KB | Output is correct |
5 | Correct | 0 ms | 40652 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40652 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40652 KB | Output is correct |
11 | Correct | 0 ms | 40652 KB | Output is correct |
12 | Correct | 0 ms | 40652 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40652 KB | Output is correct |
17 | Correct | 0 ms | 40652 KB | Output is correct |
18 | Correct | 0 ms | 40652 KB | Output is correct |
19 | Correct | 0 ms | 40652 KB | Output is correct |
20 | Correct | 0 ms | 40652 KB | Output is correct |
21 | Correct | 0 ms | 40784 KB | Output is correct |
22 | Correct | 0 ms | 40784 KB | Output is correct |
23 | Correct | 0 ms | 40652 KB | Output is correct |
24 | Correct | 0 ms | 40784 KB | Output is correct |
25 | Correct | 0 ms | 40784 KB | Output is correct |
26 | Correct | 0 ms | 40652 KB | Output is correct |
27 | Correct | 0 ms | 40784 KB | Output is correct |
28 | Correct | 0 ms | 40784 KB | Output is correct |
29 | Correct | 0 ms | 40652 KB | Output is correct |
30 | Correct | 0 ms | 40652 KB | Output is correct |
31 | Correct | 0 ms | 40784 KB | Output is correct |
32 | Correct | 0 ms | 40784 KB | Output is correct |
33 | Correct | 0 ms | 40652 KB | Output is correct |
34 | Correct | 6 ms | 40784 KB | Output is correct |
35 | Correct | 6 ms | 40784 KB | Output is correct |
36 | Correct | 9 ms | 40784 KB | Output is correct |
37 | Correct | 6 ms | 40784 KB | Output is correct |
38 | Correct | 9 ms | 40784 KB | Output is correct |
39 | Correct | 9 ms | 40784 KB | Output is correct |
40 | Correct | 9 ms | 40784 KB | Output is correct |
41 | Correct | 3 ms | 40652 KB | Output is correct |
42 | Correct | 6 ms | 40784 KB | Output is correct |
43 | Correct | 9 ms | 40784 KB | Output is correct |
44 | Correct | 6 ms | 40784 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40784 KB | Output is correct |
3 | Correct | 0 ms | 40784 KB | Output is correct |
4 | Correct | 0 ms | 40784 KB | Output is correct |
5 | Correct | 0 ms | 40784 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40784 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40784 KB | Output is correct |
11 | Correct | 0 ms | 40784 KB | Output is correct |
12 | Correct | 0 ms | 40784 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40784 KB | Output is correct |
17 | Correct | 0 ms | 40784 KB | Output is correct |
18 | Correct | 0 ms | 40784 KB | Output is correct |
19 | Correct | 0 ms | 40784 KB | Output is correct |
20 | Correct | 0 ms | 40784 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40784 KB | Output is correct |
3 | Correct | 0 ms | 40784 KB | Output is correct |
4 | Correct | 0 ms | 40784 KB | Output is correct |
5 | Correct | 0 ms | 40784 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40784 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40784 KB | Output is correct |
11 | Correct | 0 ms | 40784 KB | Output is correct |
12 | Correct | 0 ms | 40784 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40784 KB | Output is correct |
17 | Correct | 0 ms | 40784 KB | Output is correct |
18 | Correct | 0 ms | 40784 KB | Output is correct |
19 | Correct | 0 ms | 40784 KB | Output is correct |
20 | Correct | 0 ms | 40784 KB | Output is correct |
21 | Correct | 23 ms | 41444 KB | Output is correct |
22 | Correct | 36 ms | 41576 KB | Output is correct |
23 | Correct | 33 ms | 41576 KB | Output is correct |
24 | Correct | 33 ms | 41576 KB | Output is correct |
25 | Correct | 36 ms | 41576 KB | Output is correct |
26 | Correct | 6 ms | 40916 KB | Output is correct |
27 | Correct | 29 ms | 41576 KB | Output is correct |
28 | Correct | 36 ms | 41576 KB | Output is correct |
29 | Correct | 36 ms | 41576 KB | Output is correct |
30 | Correct | 33 ms | 41576 KB | Output is correct |
31 | Correct | 39 ms | 41576 KB | Output is correct |
32 | Correct | 33 ms | 41576 KB | Output is correct |
33 | Correct | 29 ms | 41576 KB | Output is correct |
34 | Correct | 36 ms | 41576 KB | Output is correct |
35 | Correct | 33 ms | 41576 KB | Output is correct |
36 | Correct | 33 ms | 41576 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 40652 KB | Output is correct |
2 | Correct | 0 ms | 40652 KB | Output is correct |
3 | Correct | 0 ms | 40652 KB | Output is correct |
4 | Correct | 0 ms | 40652 KB | Output is correct |
5 | Correct | 0 ms | 40652 KB | Output is correct |
6 | Correct | 0 ms | 40652 KB | Output is correct |
7 | Correct | 0 ms | 40652 KB | Output is correct |
8 | Correct | 0 ms | 40652 KB | Output is correct |
9 | Correct | 0 ms | 40652 KB | Output is correct |
10 | Correct | 0 ms | 40652 KB | Output is correct |
11 | Correct | 0 ms | 40652 KB | Output is correct |
12 | Correct | 0 ms | 40652 KB | Output is correct |
13 | Correct | 0 ms | 40652 KB | Output is correct |
14 | Correct | 0 ms | 40652 KB | Output is correct |
15 | Correct | 0 ms | 40652 KB | Output is correct |
16 | Correct | 0 ms | 40652 KB | Output is correct |
17 | Correct | 0 ms | 40652 KB | Output is correct |
18 | Correct | 0 ms | 40652 KB | Output is correct |
19 | Correct | 0 ms | 40652 KB | Output is correct |
20 | Correct | 0 ms | 40652 KB | Output is correct |
21 | Correct | 0 ms | 40784 KB | Output is correct |
22 | Correct | 0 ms | 40784 KB | Output is correct |
23 | Correct | 0 ms | 40652 KB | Output is correct |
24 | Correct | 0 ms | 40784 KB | Output is correct |
25 | Correct | 0 ms | 40784 KB | Output is correct |
26 | Correct | 0 ms | 40652 KB | Output is correct |
27 | Correct | 0 ms | 40784 KB | Output is correct |
28 | Correct | 0 ms | 40784 KB | Output is correct |
29 | Correct | 0 ms | 40652 KB | Output is correct |
30 | Correct | 0 ms | 40652 KB | Output is correct |
31 | Correct | 0 ms | 40784 KB | Output is correct |
32 | Correct | 0 ms | 40784 KB | Output is correct |
33 | Correct | 0 ms | 40652 KB | Output is correct |
34 | Correct | 6 ms | 40784 KB | Output is correct |
35 | Correct | 6 ms | 40784 KB | Output is correct |
36 | Correct | 9 ms | 40784 KB | Output is correct |
37 | Correct | 6 ms | 40784 KB | Output is correct |
38 | Correct | 9 ms | 40784 KB | Output is correct |
39 | Correct | 9 ms | 40784 KB | Output is correct |
40 | Correct | 9 ms | 40784 KB | Output is correct |
41 | Correct | 3 ms | 40652 KB | Output is correct |
42 | Correct | 6 ms | 40784 KB | Output is correct |
43 | Correct | 9 ms | 40784 KB | Output is correct |
44 | Correct | 6 ms | 40784 KB | Output is correct |
45 | Correct | 0 ms | 40652 KB | Output is correct |
46 | Correct | 0 ms | 40784 KB | Output is correct |
47 | Correct | 0 ms | 40784 KB | Output is correct |
48 | Correct | 0 ms | 40784 KB | Output is correct |
49 | Correct | 0 ms | 40784 KB | Output is correct |
50 | Correct | 0 ms | 40652 KB | Output is correct |
51 | Correct | 0 ms | 40652 KB | Output is correct |
52 | Correct | 0 ms | 40784 KB | Output is correct |
53 | Correct | 0 ms | 40652 KB | Output is correct |
54 | Correct | 0 ms | 40784 KB | Output is correct |
55 | Correct | 0 ms | 40784 KB | Output is correct |
56 | Correct | 0 ms | 40784 KB | Output is correct |
57 | Correct | 0 ms | 40652 KB | Output is correct |
58 | Correct | 0 ms | 40652 KB | Output is correct |
59 | Correct | 0 ms | 40652 KB | Output is correct |
60 | Correct | 0 ms | 40784 KB | Output is correct |
61 | Correct | 0 ms | 40784 KB | Output is correct |
62 | Correct | 0 ms | 40784 KB | Output is correct |
63 | Correct | 0 ms | 40784 KB | Output is correct |
64 | Correct | 0 ms | 40784 KB | Output is correct |
65 | Correct | 23 ms | 41444 KB | Output is correct |
66 | Correct | 36 ms | 41576 KB | Output is correct |
67 | Correct | 33 ms | 41576 KB | Output is correct |
68 | Correct | 33 ms | 41576 KB | Output is correct |
69 | Correct | 36 ms | 41576 KB | Output is correct |
70 | Correct | 6 ms | 40916 KB | Output is correct |
71 | Correct | 29 ms | 41576 KB | Output is correct |
72 | Correct | 36 ms | 41576 KB | Output is correct |
73 | Correct | 36 ms | 41576 KB | Output is correct |
74 | Correct | 33 ms | 41576 KB | Output is correct |
75 | Correct | 39 ms | 41576 KB | Output is correct |
76 | Correct | 33 ms | 41576 KB | Output is correct |
77 | Correct | 29 ms | 41576 KB | Output is correct |
78 | Correct | 36 ms | 41576 KB | Output is correct |
79 | Correct | 33 ms | 41576 KB | Output is correct |
80 | Correct | 33 ms | 41576 KB | Output is correct |
81 | Correct | 346 ms | 44612 KB | Output is correct |
82 | Correct | 356 ms | 44612 KB | Output is correct |
83 | Correct | 639 ms | 45404 KB | Output is correct |
84 | Correct | 446 ms | 45404 KB | Output is correct |
85 | Correct | 903 ms | 49760 KB | Output is correct |
86 | Correct | 859 ms | 49760 KB | Output is correct |
87 | Correct | 496 ms | 45404 KB | Output is correct |
88 | Correct | 793 ms | 49760 KB | Output is correct |
89 | Correct | 846 ms | 49760 KB | Output is correct |
90 | Correct | 479 ms | 48176 KB | Output is correct |
91 | Correct | 819 ms | 49364 KB | Output is correct |
92 | Correct | 926 ms | 49760 KB | Output is correct |
93 | Correct | 816 ms | 49760 KB | Output is correct |
94 | Correct | 856 ms | 49760 KB | Output is correct |
95 | Correct | 893 ms | 49760 KB | Output is correct |
96 | Correct | 803 ms | 49760 KB | Output is correct |
97 | Correct | 886 ms | 49628 KB | Output is correct |
98 | Correct | 0 ms | 40652 KB | Output is correct |