oj.uz

Submission #125270

# Submission time Handle Problem Language Result Execution time Memory
125270 2019-07-05T02:40:15 Z wilwxk Coin Collecting (JOI19_ho_t4) C++14
8 / 100
 34 ms 8412 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=1e3+5;
const ll INF=1e15+9;
vector<pair<ll, ll> > v[2];
ll dp[MAXN][MAXN];
int n;

ll dist(int a, int b, ll x) {
	if(b>=v[a].size()) return INF;
	ll resp=0;
	auto ponto=v[a][b];
	resp+=abs(ponto.first-x);
	resp+=min(abs(ponto.second-2), abs(ponto.second-1));
	return resp;
}

ll fazdp(int a, int b) {
	if(a==v[0].size()&&b==v[1].size()) return 0;
	if(a>v[0].size()||b>v[1].size()) return INF;
	if(dp[a][b]!=-1) return dp[a][b];
	// printf("calc %d %d\n", a, b);

	ll ind=(a+b)/2+1;
	dp[a][b]=INF;
	ll &cur=dp[a][b];
	cur=min(cur, fazdp(a+2, b)+dist(0, a, ind)+dist(0, a+1, ind)+1);
	cur=min(cur, fazdp(a, b+2)+dist(1, b, ind)+dist(1, b+1, ind)+1);
	cur=min(cur, fazdp(a+1, b+1)+dist(0, a, ind)+dist(1, b, ind));

	// printf("%d %d >> %lld\n", a, b, cur);
	return cur;
}

int main() {
	scanf("%d", &n); n*=2;
	memset(dp, -1, sizeof(dp));
	for(int i=1; i<=n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		if(b>=2) v[0].push_back({a, b});
		else v[1].push_back({a, b});
	}
	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());

	ll respf=fazdp(0, 0);

	printf("%lld\n", respf);
}

Compilation message

joi2019_ho_t4.cpp: In function 'll dist(int, int, ll)':
joi2019_ho_t4.cpp:12:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(b>=v[a].size()) return INF;
     ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp: In function 'll fazdp(int, int)':
joi2019_ho_t4.cpp:21:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a==v[0].size()&&b==v[1].size()) return 0;
     ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a==v[0].size()&&b==v[1].size()) return 0;
                     ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:22:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a>v[0].size()||b>v[1].size()) return INF;
     ~^~~~~~~~~~~~
joi2019_ho_t4.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a>v[0].size()||b>v[1].size()) return INF;
                    ~^~~~~~~~~~~~
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); n*=2;
  ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 9 ms 8184 KB Output is correct
13 Correct 9 ms 8184 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8188 KB Output is correct
16 Correct 9 ms 8188 KB Output is correct
17 Correct 9 ms 8188 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 11 ms 8184 KB Output is correct
20 Correct 10 ms 8184 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 9 ms 8184 KB Output is correct
23 Correct 10 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 9 ms 8184 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 8 ms 8184 KB Output is correct
28 Correct 8 ms 8184 KB Output is correct
29 Correct 9 ms 8184 KB Output is correct
30 Correct 8 ms 8248 KB Output is correct
31 Correct 9 ms 8156 KB Output is correct
32 Correct 8 ms 8184 KB Output is correct
33 Correct 9 ms 8184 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 9 ms 8184 KB Output is correct
13 Correct 9 ms 8184 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8188 KB Output is correct
16 Correct 9 ms 8188 KB Output is correct
17 Correct 9 ms 8188 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 11 ms 8184 KB Output is correct
20 Correct 10 ms 8184 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 9 ms 8184 KB Output is correct
23 Correct 10 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 9 ms 8184 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 8 ms 8184 KB Output is correct
28 Correct 8 ms 8184 KB Output is correct
29 Correct 9 ms 8184 KB Output is correct
30 Correct 8 ms 8248 KB Output is correct
31 Correct 9 ms 8156 KB Output is correct
32 Correct 8 ms 8184 KB Output is correct
33 Correct 9 ms 8184 KB Output is correct
34 Correct 34 ms 8412 KB Output is correct
35 Correct 9 ms 8312 KB Output is correct
36 Incorrect 34 ms 8312 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8184 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 9 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 9 ms 8184 KB Output is correct
13 Correct 9 ms 8184 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8188 KB Output is correct
16 Correct 9 ms 8188 KB Output is correct
17 Correct 9 ms 8188 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 11 ms 8184 KB Output is correct
20 Correct 10 ms 8184 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 9 ms 8184 KB Output is correct
23 Correct 10 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 9 ms 8184 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 8 ms 8184 KB Output is correct
28 Correct 8 ms 8184 KB Output is correct
29 Correct 9 ms 8184 KB Output is correct
30 Correct 8 ms 8248 KB Output is correct
31 Correct 9 ms 8156 KB Output is correct
32 Correct 8 ms 8184 KB Output is correct
33 Correct 9 ms 8184 KB Output is correct
34 Correct 34 ms 8412 KB Output is correct
35 Correct 9 ms 8312 KB Output is correct
36 Incorrect 34 ms 8312 KB Output isn't correct
37 Halted 0 ms 0 KB -