oj.uz

Submission #429537

# Submission time Handle Problem Language Result Execution time Memory
429537 2021-06-16T05:45:14 Z Berted Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 2 ms 460 KB 
#include <iostream>
#include <algorithm>
#include <cassert>
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long
 
using namespace std;
 
const ll INF = 1e18;
 
int N;
pii A[100001];
ll DP[2001][1001];
bool opt[2001][1001];
 
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < 2 * N; i++) cin >> A[i].fst >> A[i].snd;
	sort(A, A + 2 * N);
	
	for (int i = 1; i <= N; i++) DP[0][i] = INF;
	DP[0][0] = 0; opt[0][0] = 1;
 
	for (int i = 1; i <= 2 * N; i++)
	{
		ll val = INF;
		for (int j = 0; j <= N; j++) DP[i][j] = INF;
		for (int j = max(0, i - N); j <= i && j <= N; j++)
		{
			DP[i][j] = min(DP[i][j], DP[i - 1][j] + abs(A[i - 1].fst - i + j) + abs(A[i - 1].snd - 1));
			if (j) DP[i][j] = min(DP[i][j], DP[i - 1][j - 1] + abs(A[i - 1].fst - j) + abs(A[i - 1].snd - 2));
			val = min(val, DP[i][j]);

			//cerr << i << " " << j << " " << DP[i][j] << "\n";
		}
		
		bool yes = 0;

		for (int j = 0; j <= N; j++)
		{
			if (DP[i][j] == val) 
			{
				bool tes = opt[i - 1][j];
				if (j) tes |= opt[i - 1][j - 1];
				opt[i][j] = tes;
				yes |= tes;
			}
		}

		assert(yes);
	}
 
	cout << DP[2 * N][N] << "\n";
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Runtime error 2 ms 460 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Runtime error 2 ms 460 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Runtime error 2 ms 460 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -