Submission #62999

#	Time	Username	Problem	Language	Result	Execution time	Memory
62999		gusfring	Cultivation (JOI17_cultivation)	C++14	30 / 100	562 ms	1176 KiB

cultivation

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 305, inf = 1e9;
int n, R, C;
pii p[maxn];
vector<int> have[45];

int main(){
	scanf("%d %d %d", &R, &C, &n);
	for(int i=1; i<=n; ++i) scanf("%d%d",&p[i].X,&p[i].Y);
	int ans = inf;
	for(int up=0; up<=R; ++up)
		for(int down=0; down<=R; ++down){
			for(int row=1; row<=R; ++row) have[row].clear();
			for(int x=1; x<=n; x++)
				for(int i=max(1,p[x].X-up); i<=min(R,p[x].X+down); ++i) have[i].push_back(p[x].Y);
			for(int row=1; row<=R; ++row) sort(have[row].begin(), have[row].end());
			int left = 0, right = 0, gap = 0, bad = 0;
      for(int row=1; row<=R; ++row){
        if(have[row].size()==0){ bad = 1; break; }
        left = max(left, *have[row].begin()-1); right = max(right, C-*have[row].rbegin());
      }
      for(int row=1; row<=R; ++row) 
      	for(int i=1; i<have[row].size(); ++i)
					gap = max(gap, have[row][i]-have[row][i-1]-1-left-right);
			if(!bad) ans = min(ans, up + down + left + right + gap);
		}
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i=1; i<have[row].size(); ++i)
                     ~^~~~~~~~~~~~~~~~~
cultivation.cpp:15:7: 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:16:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; ++i) scanf("%d%d",&p[i].X,&p[i].Y);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20