oj.uz

Submission #21291

# Submission time Handle Problem Language Result Execution time Memory
21291 2017-04-12T13:47:20 Z krauch Cultivation (JOI17_cultivation) C++14
5 / 100
 0 ms 40648 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>

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 cmp(const void *ka,const void *kb) {int a=*(int *)ka;int b=*(int *)kb; return a-b;}
int uniq(int *retsu,int len) {
	qsort(retsu,len,sizeof(int),cmp);
	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 cmp2(const void *ka,const void *kb) {
	evs *a=(evs *)ka; evs *b=(evs *)kb;
	if(a->tmg<b->tmg) return 1;
	if(a->tmg>b->tmg) return -1;
	return 0;
}
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];
	}
	qsort(event,events_len,sizeof(evs),cmp2);
	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

cultivation.cpp: In function 'int main()':
cultivation.cpp:114:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cand_len;i++) for(int j=0;j<qrs_tmg[i].size();j++) {
                                           ^
cultivation.cpp:97:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&R,&C,&N);
                          ^
cultivation.cpp:98:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<N;i++) scanf("%d%d",&rs[i],&cs[i]);
                                                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40648 KB Output is correct
2 Correct 0 ms 40648 KB Output is correct
3 Correct 0 ms 40648 KB Output is correct
4 Correct 0 ms 40648 KB Output is correct
5 Correct 0 ms 40648 KB Output is correct
6 Correct 0 ms 40648 KB Output is correct
7 Correct 0 ms 40648 KB Output is correct
8 Correct 0 ms 40648 KB Output is correct
9 Correct 0 ms 40648 KB Output is correct
10 Correct 0 ms 40648 KB Output is correct
11 Correct 0 ms 40648 KB Output is correct
12 Correct 0 ms 40648 KB Output is correct
13 Correct 0 ms 40648 KB Output is correct
14 Correct 0 ms 40648 KB Output is correct
15 Correct 0 ms 40648 KB Output is correct
16 Correct 0 ms 40648 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40648 KB Output is correct
2 Correct 0 ms 40648 KB Output is correct
3 Correct 0 ms 40648 KB Output is correct
4 Correct 0 ms 40648 KB Output is correct
5 Correct 0 ms 40648 KB Output is correct
6 Correct 0 ms 40648 KB Output is correct
7 Correct 0 ms 40648 KB Output is correct
8 Correct 0 ms 40648 KB Output is correct
9 Correct 0 ms 40648 KB Output is correct
10 Correct 0 ms 40648 KB Output is correct
11 Correct 0 ms 40648 KB Output is correct
12 Correct 0 ms 40648 KB Output is correct
13 Correct 0 ms 40648 KB Output is correct
14 Correct 0 ms 40648 KB Output is correct
15 Correct 0 ms 40648 KB Output is correct
16 Correct 0 ms 40648 KB Output is correct
17 Runtime error 0 ms 40648 KB Execution killed because of forbidden syscall sysinfo (99)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40648 KB Output is correct
2 Correct 0 ms 40648 KB Output is correct
3 Correct 0 ms 40648 KB Output is correct
4 Correct 0 ms 40648 KB Output is correct
5 Correct 0 ms 40648 KB Output is correct
6 Correct 0 ms 40648 KB Output is correct
7 Correct 0 ms 40648 KB Output is correct
8 Correct 0 ms 40648 KB Output is correct
9 Correct 0 ms 40648 KB Output is correct
10 Correct 0 ms 40648 KB Output is correct
11 Correct 0 ms 40648 KB Output is correct
12 Correct 0 ms 40648 KB Output is correct
13 Correct 0 ms 40648 KB Output is correct
14 Correct 0 ms 40648 KB Output is correct
15 Correct 0 ms 40648 KB Output is correct
16 Correct 0 ms 40648 KB Output is correct
17 Runtime error 0 ms 40648 KB Execution killed because of forbidden syscall sysinfo (99)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 40648 KB Execution killed because of forbidden syscall sysinfo (99)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 40648 KB Execution killed because of forbidden syscall sysinfo (99)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40648 KB Output is correct
2 Correct 0 ms 40648 KB Output is correct
3 Correct 0 ms 40648 KB Output is correct
4 Correct 0 ms 40648 KB Output is correct
5 Correct 0 ms 40648 KB Output is correct
6 Correct 0 ms 40648 KB Output is correct
7 Correct 0 ms 40648 KB Output is correct
8 Correct 0 ms 40648 KB Output is correct
9 Correct 0 ms 40648 KB Output is correct
10 Correct 0 ms 40648 KB Output is correct
11 Correct 0 ms 40648 KB Output is correct
12 Correct 0 ms 40648 KB Output is correct
13 Correct 0 ms 40648 KB Output is correct
14 Correct 0 ms 40648 KB Output is correct
15 Correct 0 ms 40648 KB Output is correct
16 Correct 0 ms 40648 KB Output is correct
17 Runtime error 0 ms 40648 KB Execution killed because of forbidden syscall sysinfo (99)
18 Halted 0 ms 0 KB -